c++ - 查找给定字符串中的所有重复子字符串

Question

我最近遇到一个面试问题:查找给定字符串中最小大小为 2 的所有重复子字符串。该算法应该是有效的。

下面给出了上述问题的代码，但效率不高。

#include <iostream>
#include <algorithm>
#include <iterator>
#include <set>
#include <string>

using namespace std;

int main()
{
    typedef string::const_iterator iterator;
    string s("ABCFABHYIFAB");
    set<string> found;

    if (2 < s.size())
        for (iterator i = s.begin() + 1, j = s.end(); i != j; ++i)
            for (iterator x = s.begin(); x != i; ++x)
            {
                iterator tmp = mismatch(i, j, x).second;;
                if (tmp - x > 1)
                    found.insert(string(x, tmp));
            }

            copy(found.begin(), found.end(),ostream_iterator<string>(cout, "\n"));
}

我的问题是，是否有任何数据结构可以及时实现上述问题O(N)的复杂度？

如果您的答案是后缀树或散列，请详细说明。

Answer 1

如果你分析字符串“AAAAAAAAAAAAAAAA”的输出，那么里面有O(n²)个字符，所以算法至少是O(n²)。

要实现 O(n²)，只需构建 suffix tree对于 s 的每个后缀(索引 [1..n]、[2..n]、[3..n]、...、[n..n])。如果其中一个字符串没有自己的结束节点并不重要，只需计算每个节点的使用频率即可。

最后，以 count>1 遍历每个节点并打印其路径。