KMP 算法

学习笔记

我认为我这个算法可能无法讲明白，而且工作量巨大，所以为了让你快速学会我推荐学习下列笔记。

学习笔记1

学习笔记2

学习笔记3

例题

感觉经过上述的学习，你一定有所收获吧（如果没有的话还是菜就多练吧），所以接下来我会举出一些题目，应该会对你的学习有些帮助。

1.【模板】KMP（洛谷P3375）

如果你学 KMP 请先会做对这道题，这将会检验你的代码能力，请务必做对。

2.字符串中的最大值（51nod P1277）

这道题是对 KMP nxt数组 很好的应用，题意是求其所有前缀中，字符长度与出现次数的乘积的最大值。

我们可知 nxt 数组指示了当前模式串在该位置失配时，应该将模式串的哪一位与此位对齐，所以我们可以从后向前统计每个前缀的出现次数 \(res[]\)，并将 \(res[nxt[i]]+=res[i]\) ，最后再从前向后计算最大值。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+10;
ll res[N];
char b[N];
int nxt[N];
int lenb;

int main(){
    ios::sync_with_stdio(false);
	
	cin>>b+1;
	
	lenb=strlen(b+1);
	
	int j=0;
	
	for(int i=2;i<=lenb;i++){
		while(j&&b[i]!=b[j+1]){
			j=nxt[j];
		}
		if(b[i]==b[j+1]){
			j++;
		}	
		nxt[i]=j;
	}
	ll ans=0;
	
	for(int i=lenb;i>=1;i--){
		res[i]++;
		if(nxt[i]!=0){
			res[nxt[i]]+=res[i];
		}
	}
	
	for(int i=1;i<=lenb;i++){
//		cout<<res[i]<<" ";
		ans=max(ans,res[i]*i);
	} 
	cout<<ans;
    return 0;
}