14

我最近遇到一个面试问题：要找到给定字符串中最小大小为 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) 的时间复杂度实现上述问题？

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

4

3 回答 3

6

如果您分析 string 的输出"AAAAAAAAAAAAAA"，则其中有 O(n²) 个字符，因此该算法至少为 O(n²)。

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

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

于 2012-04-07T14:36:53.953 回答
2

这只是一个疯狂的想法，但值得一试（但是，它消耗 O(N) 内存，其中 N 是主字符串的长度）。该算法不是 O(N)，但也许可以优化。

这个想法是，您不想经常进行字符串比较。您可以收集读取数据的哈希值（例如读取字符的 ASCII 码总和）并比较哈希值。如果哈希值相等，则字符串可能相等（必须稍后检查）。例如：

ABCAB

A -> (65)
B -> (131, 66)
C -> (198, 133, 67)
A -> (263, 198, 132, 65)
B -> (329, 264, 198, 131, 66)

因为您只对 2+ 长度值感兴趣，所以您必须省略最后一个值（因为它始终对应于单个字符）。

我们看到两个相等的值：131 和 198。131 代表 AB 并显示货币对，但是 198 代表 ABC 和 BCA，必须通过手动检查来拒绝。

这只是想法，而不是解决方案本身。散列函数可以扩展为考虑字符在子串（或序列结构）中的位置。可以更改哈希值的存储方法以提高性能（但是以增加内存使用为代价）。

希望我能帮上一点忙：）

于 2012-04-07T14:33:48.877 回答
0

我不知道后缀树如何获取所有重复的子字符串，字符串“mississippi”构建后缀树如下：

对不起，我明白了。“最后，遍历 count>1 的每个节点并打印其路径。” “count”是这个子节点的数量

tree-->|---mississippi               m..mississippi
       |
       |---i-->|---ssi-->|---ssippi   i .. ississippi
       |       |         |
       |       |         |---ppi      issip,issipp,issippi
       |       |
       |       |---ppi                ip, ipp, ippi
       |
       |---s-->|---si-->|---ssippi    s .. ssissippi
       |       |        |
       |       |        |---ppi       ssip, ssipp, ssippi
       |       |
       |       |---i-->|---ssippi     si .. sissippi
       |               |
       |               |---ppi        sip, sipp, sippi
       |
       |---p-->|---pi                 p, pp, ppi
               |
               |---i                  p, pi

--- Suffix Tree for "mississippi" ---
于 2012-04-15T10:16:23.150 回答