c++ - 使用 C++ 的排序对引用的子字符串进行排序？

Question

我有两个长字符串(大约一百万个字符)，我想从中生成后缀并进行排序，以便找到最长的共享子字符串，因为这比暴力破解所有可能的子字符串要快得多。我最熟悉 Python，但我的快速计算估计有 40 Tb 的后缀，所以我希望可以使用 C++(建议)对每个主要不变字符串中的子字符串的引用进行排序。

我需要保留每个子字符串的索引以便稍后找到值和原始字符串，所以关于我可以使用的数据结构类型的任何建议将 1) 允许对引用字符串进行排序和 2)跟踪原始索引会非常有帮助!

当前伪代码:

//Function to make vector? of structures that contain the reference to the string and the original index
int main() {

//Declare strings
string str1="This is a very long string with some repeats of strings."
string str2="This is another string with some repeats that is very long."

//Call function to make array

//Pass vector to sort(v.begin(), v.end), somehow telling it to deference?

//Process the output in multilayer loop to find the longest exact match
// "string with some repeats"

return 0;}

Answer 1

首先，你应该为此使用一个后缀树。但我会回答你原来的问题。

C++17:

注意:使用实验性特征

您可以使用 std::string_view 来引用字符串而无需复制。这是一个示例代码:

//Declare string
char* str1 = "This is a very long string with some repeats of strings."

int main() {

    //Call function to make array
    vector<string_view> substrings;

    //example of adding substring [5,19) into vector
    substrings.push_back(string_view(str1 + 5, 19 - 5));

    //Pass vector to sort(v.begin(), v.end)
    sort(substrings.begin(), substrings.end());

    return 0;
}

C++17 之前的一切:

您可以将自定义谓词与 sort 函数一起使用。不要让你的 vector 存储实际的字符串，而是让它存储包含索引的对。

这是使其工作所需的代码示例:

//Declare string
string str1="This is a very long string with some repeats of strings."

bool pred(pair<int,int> a, pair<int,int> b){
    int substring1start=a.first,
        substring1end=a.second;
    int substring2start=b.first,
        substring2end=b.second;

    //use a for loop to manually compare substring1 and substring 2
    ...

    //return true if substring1 should go before substring2 in vector
    //otherwise return false
}

int main() {
    //Call function to make array
    vector<pair<int,int>> substrings;

    //example of adding substring [1,19) into vector
    substrings.push_back({1,19});

    //Pass vector to sort(v.begin(), v.end), passing custom predicate
    sort(substrings.begin(), substrings.end(), pred);

    return 0;
}

即使您减少了内存使用量，您的程序仍然需要 40T 迭代才能运行(因为您需要比较字符串)。除非你使用某种哈希字符串比较算法。