CyilinKMP Algorithm for Pattern Searching
作者 [@Cyilin] 2022 年 06月 09日（待更新）
给定一个字符串txt[0..n-1]和一个匹配串 pat[0..m-1]，要求我们在txt串中，找出所有匹配串出现的位置。
Examples:
Input: txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
Output: Pattern found at index 10
Input: txt[] = "AABAACAADAABAABA"
pat[] = "AABA"
Output: Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
模式搜索匹配在计算机领域是一个很重要的事情。当我们在Word文档中，在使用浏览器或者手机壳时，搜索所需要的信息是非常重要的，模式搜索匹配算法就是来呈现这些搜索数据的。
解决这种问题有一个暴力求解算法，比如说上图中我们Test长度我们设为m=16，匹配串Pattern长度设为n=4。那么我们只要考虑所有情况，比较m-n+1次，就能找到pattern串的开始位置。既然是暴力，那肯定有局限性，我们来考虑下列这种情况。
txt[] = "AAAAAAAAAAAAAAAAAB";
pat[] = "AAAAB";使用暴力解法匹配的话，以上的例子我们需要匹配到所有情况，并且每次都要遍历完整个pattern串，最坏时间复杂度达到了O(m*(n-m+1))，可以看出，最坏的情况都是伴随着匹配串经常前面匹配得好好的，最后会出现一个拖油瓶。而我们今天的主角KMP算法的时间复杂度则是O(n)。好了，铺垫了半天，主角登场了。
KMP匹配算法的基本思想是：我们在成功匹配了几个字符后，发现错误了，这时候别着急。我们已经知道的信息是发生错误前的几个字符我们都匹配成功了，那只能我们利用好这个信息点，就能减少我们的匹配次数
举一个小例子
txt = "AAAAABAAABA"
pat = "AAAA"We compare first window of txt with pat
txt = "AAAAABAAABA"
pat = "AAAA" [Initial position]
We find a match. This is same as 暴力解法.In the next step, we compare next window of txt with pat.
txt = "AAAAABAAABA"
pat = "AAAA" # 注意 这里的pat对齐方式不一样了，移动了一格
This is where KMP does optimization over Naive. In this second window, we only compare fourth A of pattern with fourth character of current window of text to decide whether current window matches or not. Since we know first three characters will anyway match, we skipped matching first three characters.Need of Preprocessing?
An important question arises from the above explanation, how to know how many characters to be skipped. To know this, we pre-process pattern and prepare an integer array lps[] that tells us the count of characters to be skipped.
Preprocessing Overview:
-
KMP算法首先要处理匹配串pat，并且建立一个辅助长度也为m的数组lps[]用来在匹配时跳过已匹配好的字符串
-
name \lps** indicates longest proper prefix which is also suffix.（前缀和后缀最长交集的长度）.A proper prefix is prefix with whole string not** allowed. For example, prefixes of “ABC” are “”, “A”, “AB” . Proper prefixes are “”, “A” and “AB”. Suffixes of the string are “”, “C”, “BC”.
注：请注意，很明显我们这里的前缀后缀是不把整个字符串包含在内的，因此"ABC"既不是前缀也不是后缀。
Examples of lps[] construction:
For the pattern “AAAA”,
lps[] is [0, 1, 2, 3]
# 仔细说明下，
lps[0]==>考虑"A" ==>前后缀交集为空 ==>0
lps[1]==>考虑"AA" ==>前后缀交集为"A" ==>1
lps[2]==>考虑"AAA" ==>前后缀交集为"AA" ==>2
lps[3]==>考虑"AAAA" ==>前后缀交集为"AAA"==>3
For the pattern “ABCDE”,
lps[] is [0, 0, 0, 0, 0]
For the pattern “AABAACAABAA”,
lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
For the pattern “AAACAAAAAC”,
lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]
For the pattern “AAABAAA”,
lps[] is [0, 1, 2, 0, 1, 2, 3]Searching Algorithm:
我们上小节构造的lps数组是怎么是确定下一个匹配位置的呢，也就是说，怎么知道哪些已匹配的字符需要被跳过呢？
- 我们首先从匹配串的第一个位置开始，即pat[j] with j=0.
- 接着继续匹配，如果不遇到mismatch，那么i和j将会同步进行自增。
- 天下无不散宴席，匹配失败了
- 如果此时j=0，即第一个字符就对不上，那没辙，i++
- 如果此时j≠0，令重置j=lps[j-1]，重新匹配（核心步骤）
- 如果此时j=M，代表这次匹配成功，输出i的值，然后重置j=lps[j-1]，继续匹配
下列给个实际例子，边走可以边参考上面的步骤，慢慢地就可以理解这个过程。
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
lps[] = {0, 1, 2, 3}
i = 0, j = 0
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
匹配成功 i++ j++
i = 1, j = 1
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
匹配成功 i++ j++
i = 2, j = 2
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
匹配成功 i++ j++
i = 3, j = 3
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
匹配成功 i++ j++
i = 4, j = 4
由于j==M 输出当前的i-m+1值并且重置j，这里的重置就要依靠我们的lps数组
j = lps[j-1] = lps[3] = 3
这里就不像暴力解法，我们没有回退到最开始令j=0，而是定为了3
而j的位置由lps[j-1]的值来确定，就像上一步我们所做的。
**为什么要回到3呢，为什么我们要计算lps数组呢？我们这样在干什么**
仔细观察下面的例子，回到j=3的时候，**前面的字串全是匹配成功的**，
这里就直观地体现了我们优于暴力解法的地方，少匹配了三次。
i = 4, j = 3
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
匹配成功 i++ j++
i = 5, j = 4
由于j==M 输出i-m+1的值并且重置j（i-m+1代表串出现的位置）
j = lps[j-1] = lps[3] = 3
i = 5, j = 3
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
匹配不成功，此时i不动，只改变j的值
j = lps[j-1] = lps[2] = 2
i = 5, j = 2
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
匹配不成功，此时i不动，只改变j的值
j = lps[j-1] = lps[1] = 1
i = 5, j = 1
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
匹配不成功，此时i不动，只改变j的值
j = lps[j-1] = lps[0] = 0
i = 5, j = 0
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
匹配还是不成功，但是此时j=0，我们要进行i++
i = 6, j = 0
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
匹配成功 i++ j++
i = 7, j = 1
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
匹配成功 i++ j++
i = 8, j = 2
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
匹配成功 i++ j++
i = 9, j = 3
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
匹配失败
continuing...模拟过程比较长，我们来具体分析一处的失配情况。以图中的例子来说，在 i 处失配，那么主字符串和模式字符串的前边6位就是相同的。又因为模式字符串的前6位，它的前4位前缀和后4位后缀是相同的（j=lps[j-1]=4)，所以我们推知主字符串i之前的4位和模式字符串开头的4位是相同的。就是图中的灰色部分。那这部分就不用再比较了。注意，在整个过程中，指针i是不回溯的。
代码实现
整理一下头绪，我们现在需要什么？
lps数组，因为没有它，匹配的时候无法决定到底跳过哪些字符。
进入代码之前，深呼吸，前方高能
强调亿点：lps[i]指的是从[0,i]的公共最长前后缀的长度
循序渐进，先来点简单的，我们从实现lps数组开始。
1392. 最长快乐前缀
class Solution{
public:
string longestPrefix(string s) {
int m = s.length();
int lps[m];
lps[0] = 0;
for(int i = 0,j = 1;i < m;i++){
while(j>0 && s[i]!=s[j]){
j=next[j-1];
}
if(s[i]==s[j]){
++j;
}
lps[i] = j;
}
return s.substr(0,lps[m-1]);
}
}为什么设i=1，j=0困扰了我很久，走了很多弯路，直到我在知乎某评论里看到一句话
其实，求next数组的过程完全可以看成字符串匹配的过程，即以模式字符串为主字符串，以模式字符串的前缀为目标字符串.
lps数组的计算，我理解是p串错开一位匹配，0起始的p串与1起始的p串，前者是瞄准了p的后缀，后者抛弃了p[0]所以是瞄准p的前缀，双方的公共部分即是公共前后缀。
28. 实现 strStr()
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
if (m == 0) return 0;
vector<int> lps(m,0);
calLPS(needle, lps); // 计算LPS数组
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j]) {
j = lps[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j == m) {
return i - m + 1;
}
}
return -1;
}
void calLPS(const string &needle,vector<int> &lps){
for (int i = 1, j = 0; i < needle.length(); i++) {
while (j > 0 && needle[i] != needle[j]) {
// 匹配不上，代表现在的前缀肯定匹配不了后缀了
// 反求一下，前面已匹配的前缀里相同的子前缀
j = lps[j - 1];
}
if (needle[i] == needle[j]) {
// 如果下一位相同，更新相同的lps
j++;
}
lps[i] = j;
}
}
};459. 重复的子字符串
算法改进
没想到吧，都这么复杂了，竟然还有改进。没办法，聪明的数学家和程序员们太多了，不过站在巨人的肩膀上，我认为不应该感到厌烦，而是得抱着感恩之心。