KMP算法

2025年3月19日

KMP算法

我觉得还做不出题，想不通源码，先放着，wiki在这里：KMP算法

基本概念-next数组

前缀：不含最后一个字符但包含第一个字符的所有字串后缀：不含第一个字符但包含最后一个字符，的所有字串前缀表 next ：代表 p[0:i] 即 p 的前 i+1 的字符，最长相等前后缀的长度,即前后缀的最长相同字串的长度。如：假设模式串 P = "ABABCABAA"，我们来计算 next 数组。

位置 `i`	P[i]	`P[0:i]` (子串)	`next[i]`	解释
0	A	A	0	只有一个字符，无前后缀
1	B	AB	0	”A”（前缀） ≠ “B”（后缀）
2	A	ABA	1	”A”（前缀）= “A”（后缀），长度 1
3	B	ABAB	2	”AB”（前缀）= “AB”（后缀），长度 2
4	C	ABABC	0	”ABAB” ≠ “BABC”，无相等前后缀
5	A	ABABCA	1	”A”（前缀）= “A”（后缀），长度 1
6	B	ABABCAB	2	”AB”（前缀）= “AB”（后缀），长度 2
7	A	ABABCABA	3	”ABA”（前缀）= “ABA”（后缀），长度 3
8	A	ABABCABAA	1	”A”（前缀）= “A”（后缀），长度 1

如何构建呢？可以用一个循环，一个先计算前缀最长的长度，如果失配就重新移动字符匹配，保留最大值。实现：这里参考KMP算法next数组的优化过程

vector<int>Next(const string &p){
	int m=p.size();
	vector<int>next(m,0);
	int j=0;

	 for(int i=1;i<m-1;i++){
		 while(j>0 && p[i]!=p[j]){
			 j=next[j-1];//失配，变成前一个匹配的位置。
		 }
		 if(p[i]==p[j]) j++;//配对，记录最长长度增加
		 next[i]=j;
	 }
	 return next;
	}

KMP算法比较

给定一个文本 t 和一个字符串 s，我们尝试找到并展示 s 在 t 中的所有出现（occurrence）。为了简便起见，我们用 n 表示字符串 s 的长度，用 m 表示文本 t 的长度。我们构造一个字符串 s + # + t，其中 # 为一个既不出现在 s 中也不出现在 t 中的分隔符。接下来计算该字符串的前缀函数。现在考虑该前缀函数除去最开始 n + 1 个值（即属于字符串 s 和分隔符的函数值）后其余函数值的意义。根据定义，next[i] 为右端点在 i 且同时为一个前缀的最长真子串的长度，具体到我们的这种情况下，其值为与 s 的前缀相同且右端点位于 i 的最长子串的长度。由于分隔符的存在，该长度不可能超过 n。而如果等式 next[i] = n 成立，则意味着 s 完整出现在该位置（即其右端点位于位置 i）。注意该位置的下标是对字符串 s + # + t 而言的。因此如果在某一位置 i 有 π[i] = n 成立，则字符串 s 在字符串 t 的 i − (n − 1) − (n + 1) = i − 2n 处出现。

这是oier算法，其实我想不出来：

vector<int>search(string t,string s){
	string cur = s+'#'+t;
	int sz1=t.size(),sz2=s.size();
	vector<int> v;
	vector<int>next=Next(cur)
	for(int i=sz2+1;i<=sz2+sz1;i++){
		if(next[i]==sz2) v.push_back(i-2*sz2);
	}
	return v;
}

KMP 算法的想法是：设法利用这个已知信息，不要把「搜索位置」移回已经比较过的位置，继续把它向后移，这样就提高了效率。整个 KMP 算法中核心且难理解的是：

部分匹配表代码实现，理解不了。原理理解了，但是代码想不明白
当不匹配的时候，不源字符串不回溯，只根据部分匹配表，移动子串的下标，让子串回溯。

所以用简单的模拟的话，是这样的：

vector<int>KMP(string s,string p){
    int sz1=s.size(),sz2=p.size();
    vector<int>Next=getnext(p);
    vector<int>v;
    for(int i=0,j=0;i<sz1;i++){
        if(s[i]==p[j]){
            j++;
        }
         else if(j>0){
            j=Next[j-1];
            i--;//这里回溯j，是KMP算法的核心思路。
        }
        if(j==sz2){
            v.push_back(i-j+1);
            j=Next[j-1];
        }
    }
    return v;    
}

用 for 来一个一个匹配都懂，这里 KMP 算法核心就算那个回溯 j 和 push_back(i-j+1) 。至于为什么需要回溯j，这是KMP算法的核心思想，让我解释一下：

为什么要回溯j的原因

当我们在匹配过程中遇到不匹配的字符时，传统的字符串匹配算法会将模式串完全重置到开始位置，然后主串向前移动一位重新开始匹配。这样会导致很多已经比较过的字符被重新比较，效率很低。

KMP算法的核心优化在于： 利用已知信息：当匹配失败时，我们已经知道了模式串的前j个字符与主串的相应部分是匹配的。 避免重复工作：我们不需要完全回到模式串的起始位置，而是可以跳到一个中间位置，这个位置由Next数组决定。 Next数组的含义：Next[j-1]表示当模式串的第j个字符不匹配时，应该将模式串指针j回退到哪个位置，使得模式串的开头部分与主串的当前部分潜在地匹配。

简单来说，回溯j使我们可以：

充分利用已经获得的部分匹配信息
避免从头开始重新匹配模式串
实现线性时间复杂度的字符串查找

这种”聪明地跳过”是KMP算法比朴素字符串匹配算法更高效的关键原因。

为什么要返回 i-j+1 的位置

关于为什么返回的是 i-j+1 而不是 i 的位置，这是因为在KMP算法中，当我们找到一个完全匹配时：

i 指向的是主串中刚刚匹配完成的最后一个字符的位置（当前循环结束后）。
j 等于模式串的长度 sz2，表示模式串已经完全匹配，所以这里把j 写作sz2没有任何问题。
我们需要返回的是匹配开始的位置，而不是结束的位置。

计算匹配开始位置的公式是：

匹配起始位置 = 当前位置(i) - 模式串长度(j) + 1

具体分析：

假设主串是 “ABCDEF”，模式串是 “CDE”
当匹配完成时，i 指向 ‘E’（索引4），j 等于3
匹配的起始位置应该是 ‘C’（索引2）
索引计算：4 - 3 + 1 = 2

在这里的for循环实现中，因为循环结束后 i 会自增，所以 i 实际上指向的是匹配完成后的下一个字符位置，为了避免这种错误运算，我们在每次错误匹配回溯的时候，都做一次 i—，让 i 回到匹配完成的最后一个位置。因此，正确的计算是 i-j+1。

总体实现代码：

vector<int>getnext(string s){
    int n=s.size();
    int j=0;//前缀
    vector<int>next(n,0);
    for(int i=1;i<n;i++){//后缀
        while(j>0&&s[i]!=s[j]) j=next[j-1];
        if(s[j]==s[i]) j++;
        next[i]=j;
    }
    return next;
}
vector<int>KMP(string s,string p){
    int sz1=s.size(),sz2=p.size();
    vector<int>next=getnext(p);
    vector<int>v;
    for(int i=0,j=0;i<sz1;i++){
        if(s[i]==p[j]){
            j++;
        }
         else if(j>0){
            j=Next[j-1];
            i--;
        }
        if(j==sz2){
            v.push_back(i-j+1);
            j=Next[j-1];
        }
    }
    return v;    
}

  

int main(){
    string s,p;
    cin>>s>>p;
    vector<int>ans=KMP(s,p);
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]+1<<endl;
    }
    vector<int>Next=next(p);
    for(int i=0;i<Next.size();i++){
        cout<<Next[i]<<" ";
    }
    return 0;
}

题目：洛谷KMP模板题