c - 用于查找 2 个字符串之间任意长度的所有共享子字符串，然后计算字符串 2 中出现次数的算法？

Question

我遇到了一个不寻常的挑战，到目前为止我无法确定最有效的算法来解决这个问题。

---

以下面2个字符串为例，找出2个任意长度的字符串之间所有共有的共享子串，并统计所有这些共享子串在字符串2中出现的次数。你的算法也需要能够计算包含大小高达 100MB 或更大字符串的文件之间的共享子字符串。

例子:

字符串 1:ABCDE512ABC361EG51D

字符串 2:ADE5AHDW4131EG1DG5C

给定这 2 个字符串，该算法将找到以下共享子字符串:A,C,D,E,5,1,3,G,DE,E5,EG,G5,1D,DE5,1EG

然后从这些共同共享的子串中，我们会发现每个子串在字符串 2 中出现了多少次。

A: 在字符串 2 中出现 2 次

C: 在字符串 2 中出现 1 次

D: 在字符串 2 中出现 3 次

等..

---

我为解决这个问题而采取的第一种方法是使用 2 个嵌套的 for 循环通过计算公共(public)共享子串来强制我的方式 - 显然效率最低，但这是一种快速而肮脏的方式来了解什么预期的输出应该具有较小的测试输入和最慢的运行时间，大约需要 2 分钟来计算 2 个包含大小为 50kb 的 ascii 字符串的文件之间的所有公共(public)共享子字符串。将大小增加到 1mb 会使计算戛然而止，因为必须进行大量的嵌套迭代来计算它。

下一个方法是使用树——看看我可以折衷多少内存来优化计算时间。这种方法要快得多。同样的两个 50kb 的文件，用蛮力方法花费 2 分钟，几乎是即时的。运行 1mb 文件仍然非常快(秒)，但随着我继续测试越来越大的文件大小，由于树的大小，我很快开始遇到内存问题。

---

注意:字符串文件将只包含 ASCII 字符!

---

编辑:

我正在进一步升级，请参阅:

https://gist.github.com/braydo25/f7a9ce7ce7ad7c5fb11ec511887789bc

Answer 1

这里有一些代码说明了我在上面的评论中提出的想法。虽然它是可运行的 C++ 代码，但从某种意义上说，它更像是伪代码，因为所使用的数据结构肯定不是最优的，但它们允许对算法有清晰的认识。

struct Occurrence
{
    //The vectors contain indices to the first character of the occurrence in ...
    std::vector<size_t> s1;  // ... string 1 and ...
    std::vector<size_t> s2;  // ... string 2.
};

int main()
{
    //If you cannot load the entire strings in memory, a memory-mapped file might be
    //worth considering
    std::string s1 = "ABCDE512ABC361EG51D";
    std::string s2 = "ADE5AHDW4131EG1DG5C";

    //These vectors store the occurrences of substrings for the current and next length
    std::vector<Occurrence> occurrences, nextOccurrences;
    int length = 1;

    std::map<char, Occurrence> occurrenceMap;
    //Initialize occurrences
    for (int i = 0; i < s1.length(); ++i)
        occurrenceMap[s1[i]].s1.push_back(i);
    for (int i = 0; i < s2.length(); ++i)
        occurrenceMap[s2[i]].s2.push_back(i);

    for (auto& pair : occurrenceMap)
    {
        if (pair.second.s1.size() > 0 && pair.second.s2.size() > 0)
            occurrences.push_back(std::move(pair.second));
    }

    do
    {
        nextOccurrences.clear();

        std::cout << "Length " << length << std::endl;
        for(auto& o : occurrences)
        {
            std::cout << std::string(s1.c_str() + o.s1[0], length) << " occurred "
                      << o.s1.size() << " / " << o.s2.size() << " times." << std::endl;

            //Expand the occurrence
            occurrenceMap.clear();
            for (auto p : o.s1)
            {
                if (p + length < s1.length())
                    occurrenceMap[s1[p + length]].s1.push_back(p);
            }                   
            for (auto p : o.s2)
            {
                if (p + length < s2.length())
                occurrenceMap[s2[p + length]].s2.push_back(p);
            }
            for (auto& pair : occurrenceMap)
            {
                if (pair.second.s1.size() > 0 && pair.second.s2.size() > 0)
                    nextOccurrences.push_back(std::move(pair.second));
            }
        }

        ++length;
        std::swap(occurrences, nextOccurrences);

    } while (!occurrences.empty());


    return 0;
}

输出:

Length 1
1 occurred 3 / 3 times.
3 occurred 1 / 1 times.
5 occurred 2 / 2 times.
A occurred 2 / 2 times.
C occurred 2 / 1 times.
D occurred 2 / 3 times.
E occurred 2 / 2 times.
G occurred 1 / 2 times.
Length 2
1D occurred 1 / 1 times.
1E occurred 1 / 1 times.
DE occurred 1 / 1 times.
E5 occurred 1 / 1 times.
EG occurred 1 / 1 times.
G5 occurred 1 / 1 times.
Length 3
1EG occurred 1 / 1 times.
DE5 occurred 1 / 1 times.

初始化期间将使用最多的内存，因为两个输入字符串的每个字符都会有一个条目。如果知道字符串的大致长度，则可以选择比 size_t 更合适的索引数据类型。所需的内存量按输入大小的顺序排列。所以两个100MB的文件对于普通电脑应该是没有问题的。在初始化之后(更具体地说，在循环的第一次迭代之后)，这些数据中的大部分将被删除，因为不再需要它们。