【模板】KMP

字符串算法中最有名的一个算法之一。 属于单模式匹配算法，主要用于处理字符串S1中是否出现字符串S2。 核心内容为next数组，用于处理字符串S2的跳跃。

next数组

相当于失配指针，意思是当匹配不上的时候，字符串跳跃的位置，这就避免了进行过多的匹配。

适配指针的构建就是字符串前缀匹配的过程。

while(i<b.length())
	{
		if( b[p]==b[i] )
		{
			p++;
			n[i]=p;
			i++;
		 }
		 else{
		 	if(p==0)
		 	{
			 n[i]=p;
		 	i++;}
		 	else p=n[p-1];
		 }
	}

Code

#include<bits/stdc++.h>
using namespace std;
string a,b;
int n[30012];
int main(){
	cin>>a>>b;
	int i=1,p=0;
	while(i<b.length())
	{
		if( b[p]==b[i] )
		{
			p++;
			n[i]=p;
			i++;
		 }
		 else{
		 	if(p==0)
		 	{
			 n[i]=p;
		 	i++;}
		 	else p=n[p-1];
		 }
	}
	i=0;int j=0;
	while(i<a.length())
	{
		if(a[i]==b[j]) i++,j++;
		else if( j==0 ) i++;
		else j=n[j-1];
		if( j==b.length() ) cout<<i-j+1<<endl,j=n[j-1];
	}
	for(int k=0;k<b.length();k++)
	cout<<n[k]<<" ";
	
}