• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【模板】KMP字符串匹配

开发技术 开发技术 6小时前 3次浏览

RT

#include<bits/stdc++.h>
using namespace std;

inline int read()
{
	register int x=0,w=1;
	register char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-'){ch=getchar();w=-1;	}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();	}
	return x*w;
}
int l1,l2,p[2000010],ans[2000010],cnt;
string s1,s2; 
int main()
{
	cin>>s1>>s2;
//    getline(cin,s1);getline(cin,s2);
    l1=s1.size();l2=s2.size();
    for(int i=1,j=0;i<l2;++i)
    {
    	while(j&&s2[j]!=s2[i]) j=p[j-1];
    	if(s2[j]==s2[i]) j++;
    	p[i]=j;
    }
    for(int i=0,j=0;i<l1;++i){
    	while(j&&s2[j]!=s1[i]) j=p[j-1];
    	if(s2[j]==s1[i]) j++;
    	if(j==l2){
    		ans[++cnt]=i-j+1;
    		j=p[j-1];
    	}
    }
    for(int i=1;i<=cnt;++i) cout<<ans[i]+1<<endl;
    for(int i=0;i<l2;++i) cout<<p[i]<<" ";
	return 0;
}

程序员灯塔
转载请注明原文链接:【模板】KMP字符串匹配
喜欢 (0)