有彩蛋

题意

kmp 模板(递推最长前后缀长度+ kmp 匹配)

思路

模板题,主要看代码

可以看这个视频了解过程

代码

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
string a,b;
int la,lb;
int f[N];
void border()
{
	int j=0;
	for(int i=1;i<lb;i++)//注意从1开始
	{
		while(j && b[i]!=b[j])//直到找到不匹配的
			j=f[j-1];
		if(b[i]==b[j])
			j++;
		f[i]=j;
	}
}
void kmp()
{
	int j=0;
	for(int i=0;i<la;i++)//注意从0开始
	{
		while(j && a[i]!=b[j])
			j=f[j-1];
		if(a[i]==b[j])
			j++;
		if(j==lb)
		{
			cout<<i-lb+2<<"\n";//因为i和j是从0开始的,但是输出的是从1开始的,所以要+1+1=2
            j=f[j-1];
		}
	}
}
int main()
{
	cin>>a>>b;
    la=a.size();
    lb=b.size();
	border();
	kmp();
	for(int i=0;i<lb;i++)
		cout<<f[i]<<" ";
	return 0;
}

彩蛋

哈希好用

#include<bits/stdc++.h>
#define N 1000005
#define P 12289
using namespace std;
string a,b;
int bd[N];
int p[N];
int ha[N];
int hb[N];
int hashf(int l,int r)
{
    return ha[r]-ha[l-1]*p[r-l+1];
}
int main()
{
    p[0]=1;
    for(int i=1;i<N;i++)
        p[i]=p[i-1]*P;
    cin>>a>>b;
    for(int i=1;i<=a.size();i++)
        ha[i]=ha[i-1]*P+a[i-1];
    for(int i=1;i<=b.size();i++)
        hb[i]=hb[i-1]*P+b[i-1];
    for(int i=0;i<=a.size()-b.size();i++)
    {
        if(hashf(i+1,i+b.size())==hb[b.size()])
            cout<<i+1<<"\n";
    }
    for(int i=1,j=0;i<b.size();i++)
    {
        while(j>0 && b[i]!=b[j]) j=bd[j-1];
        if(b[i]==b[j]) j++;
        bd[i]=j;
    }
    for(int i=0;i<b.size();i++)
        cout<<bd[i]<<" ";
    return 0;
}

声明

我不是题解，我这是体节。

要学习，不要看我，作者有空再写个题解。

（这个只是炫耀一下作者不用分隔符的kmp）

代码

#include<iostream>
using namespace std;
int main(){
	string s("");
	string t("");
	cin>>s>>t;
	string a(t+s);
	int m(t.size());
	int len(a.size());
	int*f(new int[len]{});
	int j(0);
	for(int i(1);i<len;i++){
		while(j>0&&a[i]!=a[j])
			j=f[j-1];
		if(a[i]==a[j])
			j++;
		f[i]=j;
		if(i==m)
			f[i]=0; 
		if(i>2*m-2&&f[i]>=m){
			cout<<i-2*m+2<<'\n';
			j=f[j-1];
		}
	}
	for(int i(0);i<m;i++)
		cout<<f[i]<<' ';
	delete f;
	return 0;
}