KMP算法，不能理解

Question

我很难理解KMP算法。我知道前缀-后缀是什么，所以我写了计算前缀-后缀表的代码：

 private int[] calculatePrefSuffArray(String pattern) {
    char patternArray[] = pattern.toCharArray();
    int tab[] = new int[pattern.length()];
    tab[0] = 0;
    int t = tab[0];
    for (int i = 1; i < pattern.length(); i++) { // t = tab[i-1]
        while(t >0 && patternArray[i] != patternArray[t] ) {
            t = tab[t-1];
        }
        if(patternArray[i] == patternArray[t]) t++;
        tab[i] = t;
    }
    return tab;
}

但我不明白如何在KMP中使用它。有人能给我解释一下吗？

Answer 1

朴素算法

在正常的模式匹配算法中，如果你有一个长度为m的模式和一个长度为n的文本，那么模式中的m个字符通常会与文本中的n个字符进行匹配，不过如果已经发生了不匹配，你可以使用一个出口函数来避免一些匹配，从而稍微绕过这种行为。

因此，该算法的渐近复杂度为O(mn)。

但朴素算法的问题是，它不会试图理解模式的任何内容。例如，如果你在一家公司工作了5年，你可以以某种方式利用这5年的经验。同样，我们可以分析子字符串并推断出有关这方面的一些有用信息。这正是您在计算前缀函数时所做的事情。

KMP算法

​

​

既然我们已经找到了与文本匹配的模式的子串，那么将模式向右滑动6(找到子串的位置)-1(位置6的前缀函数)不是更好，然后立即重新开始比较，而不是再次走天真的方式吗？事实上，前缀函数值是用来确定模式必须向右滑动多少次的。这一开始可能有点难理解，但请拿一张纸，将一个小文本与一个写下所有变量的中间值的小模式进行比较，然后你就会意识到这个算法是多么的漂亮。

该算法的渐近复杂度为O(m+n)，因为每次发生不匹配时，我们都会滑过该模式。

算法的c++实现如下:

程序1：创建一个大小为10000000的图案，并将其存储在文件inputtext.txt中(您可以更改大小。也许吧！)

#include<iostream>
#include<fstream>
#include<cstdlib>

using namespace std;

  main()
  {
    ofstream myfile("inputtext.txt");
    char *intxt="abcd"; // I wish the sample text to contain only these alphabets
    long int i=0;
    char* txt = new char[10000000];
    while(i<10000000)
       {
       txt[i]=intxt[(rand()%4)]; 
       i++;
       }
   myfile<<txt;
   myfile.close();
  }

Program2：使用KMP算法进行模式搜索。

#include<iostream>
#include<string>
#include<fstream>
using namespace std;

 void prefix_fn(int* p, char* s)
 {
 s--;
 p--;
 int i,k=0;
   p[1]=0;
   for(i=2;i<=7;i++)
   {
     while ((k>0)&&(s[k+1]!=s[i]))
         k=p[k];
     if (s[k+1]==s[i])     
         k++;
     p[i]=k;
   }
 }
main()
{
int i,k;
int *p= new int[7];
char* txt=new char[10000000];
ifstream myfile("inputtext.txt");
myfile.seekg(0,ios::beg);

myfile.read(txt,10000000);
myfile.close();
char *s="abdcbab";
cout<<"Prefix Table"<<endl;
prefix_fn(p,s);
p--; // This helps to start indexing from 1, just for me to avoid confusion
s--; // Similar objective as stated above.
   for(int i=1;i<=7;i++)
      cout<<p[i]<<endl;
txt--;
k=0;
  for(i=1;i<=10000000;i++)
    {
       while(k>0 && s[k+1]!=txt[i])
           {
            k=p[k]; 
           }
       if(s[k+1]==txt[i])
           {
            k=k+1;
           }
        if(k==7)
           {
            cout<<"Match found at position : "<<i-6<<endl;
            k=p[k]; 
           }
    }
p++;
delete[] p; 
txt++;
delete[] txt; //deleting the memory allocated.
}

希望这能对你有所帮助。

Answer 2

您的calculatePrefSuffArray("ABC ABCDAB ABCDABCDABDE")将返回以下内容

[0  0  0  0  1  2  3  0  1  2  0  1  2  3  0  1  2  3  0  1  2  0  0]

而不是这个

[-1  0  0  0  1  2  3  0  1  2  0  1  2  3  0  1  2  3  0  1  2  0  0 ]

通过替换以下代码来更正代码

tab[0] = 0;
int t = tab[0];

有了这个

tab[0] = -1;
tab[1] = 0;
int t = tab[1];

传递从calculatePrefSuffArray(String pattern)函数返回的创建的int[] table。

如果在string文本中找到word，它将返回true。

private boolean search(String string, String word, int[] table) {
    int m = 0, i = 0;
    while ((m + i) < string.length()) {
        if (word.charAt(i) == string.charAt(m + i)) {
            if (i == word.length() - 1) {
                return true;
            }
            i++;
        } else {
            if (table[i] > -1) {
                m = m + i - table[i];
                i = table[i];
            } else {
                i = 0;
                m++;
            }
        }
    }
    return false;
}

如果您在理解代码方面有任何问题，请告诉我。

Answer 3

afzalex很好地解释了这一点。

但是如果你现在还不清楚，那么我发现这篇文章很容易理解。可能会有帮助：http://www.algorithmwebschool.com/index.php/kmp-algorithm/