KMP算法

定义

---

KMP算法

KMP算法，即Knuth–Morris–Pratt算法，利用前缀函数高效搜索字符串中的模式。

过程

---

定义i, j两个指针，i用于匹配字符串，j用于匹配模式，初始时i = 0, j = 0`。

pattern[i] == pattern[j]时，匹配成功，j++。

pattern[i] != pattern[j]时，匹配失败，若j != 0（即存在已经匹配的前缀pattern[0...j - 1]），此时有pattern[0...j - 1] == str[i - j...i - 1]。
此时str[i - j...i - 1]（也就是pattern[0...j - 1]）无法作为pattern[i]和str[j]的共同前缀，因此需要在pattern[0...j - 1]中找到一个最长真前缀（这个前缀同时也是pattern[i - j...i - 1]（也就是pattern[0...j - 1]）的最长真后缀）使得pattern[i] == str[j]，即需要找到pattern[0...j - 1]的最长真前缀真后缀，所以令j = lsp[j - 1]，若依然pattern[i] != str[j]，重复上述操作，直至匹配成功（j++）或j == 0。

若j == 模式长度，匹配完成，若要继续搜索，令j = lsp[j - 1]（即模式本身的最大真前缀真后缀作为已匹配的前缀）即可。

实现

---

int N, lps[N];  \\ lps[i]默认为0
 
void LPS(string pattern)  
{  
    for (int i = 1, j = 0; i < pattern.size(); i++)  
    {  
       while (j > 0 && pattern[i] != pattern[j])  
          j = lps[j - 1];  
       if (pattern[i] == pattern[j])  
          lps[i] = ++j;  
    }  
}  
  
void KMP(string str, string pattern)  
{  
    LPS(pattern);  
    for (int i = 0, j = 0; i < str.size(); i++)  
    {  
       while (j > 0 && str[i] != pattern[j])  
          j = lps[j - 1];  
       if (str[i] == pattern[j])  
          j++;  
       if (j == pattern.size())  
       {  
          cout << i - pattern.size() + 2 << endl;  
          j = lps[j - 1];  
       }  
    }  
}