使用Knuth-Morris-Pratt算法查找不同的子串

Question

我正在学习KMP字符串匹配算法，以便在给定的字符串中找到模式的总出现次数。我的部分代码如下，用java实现：

void kmpMatcher( string text, string pattern) {
    int counter = 0;
    int n=text.length();
    int m=pattern.length();
    int [] pi = computePrefix(); // computes the prefix array
    int q = 0;
    for (int i=0;i<n;i++) {
        while(q > 0 && pattern.charAt(q) != text.charAt(i)) q = pi[q-1];
        if (pattern.charAt(q) == text.charAt(i)) q++;
        if (q==m) {
            out.println(i-m+1);
            q = pi[q-1];
            counter++;
        }
    }
    out.println("Total matches: " + counter);
} 

有没有办法使用上面的函数在给定的输入文本字符串中找到不同的子串的总数？找到不同的子字符串的逻辑是什么？

Answer 1

您可以在O(N^2)时间内完成此操作(这比将所有子字符串添加到例如i哈希表的朴素解决方案要好)：

1. 让我们遍历字符串S的所有满足条件。
2. 对于字符串的每个后缀T，我们可以构建一个T#S字符串并计算它的前缀函数。
3. 我们可以通过查看prefix函数数组并找到满足以下条件的最大后缀来找到作为T的前缀且不是任何更长后缀的前缀的子字符串的数量。
4. 现在，我们只需将所有后缀的此类子字符串的数量相加。

如果您需要更快的解决方案(如O(N)或O(N log N))，您可以使用后缀结构(如后缀自动机或后缀数组)，但这些解决方案更为复杂。