KMP+Tire树(模板)

\(\color{Red}{KMP板子}\)

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e6+9;

int la,lb,j,kmp[maxn];

char a[maxn],b[maxn];

int main()

{

	cin>>a+1>>b+1;

	la=strlen(a+1),lb=strlen(b+1);

	for(int i=2;i<=lb;i++)//第一为默认为0

	{

		while(j&&b[i]!=b[j+1])	j=kmp[j];

		//ABCA的相同前后缀是A，如果想再增加

		//必须再添加一个B,也就是b[j+1]位置要等于b[i]

		if(b[j+1]==b[i])	j++;

		kmp[i]=j;

	}

	j=0;

	for(int i=1;i<=la;i++)

	{

		while(j&&b[j+1]!=a[i])	j=kmp[j];

		if(b[j+1]==a[i])	j++;

		if(j==lb)

		{

			cout<<i-lb+1<<endl;

			j=kmp[j];//找到后开始找下一个

		}

	}

	for(int i=1;i<=lb;i++)	cout<<kmp[i]<<" ";

}

\(\color{Red}{Tire树板子}\)

struct node{

	int zi[27];

}tire[maxn];int isok[maxn],tot;

void insert(string s)

{

	int now=0,len=s.length();

	for(int i=0;i<len;i++)

	{

		int ch=s[i]-'a'+1;

		if(!tire[now].zi[ch])

			tire[now].zi[ch]=++tot;

		now=tire[now].zi[ch];

	}

	isok[now]=1;//此节点是一个字串

}

bool ask(string s)

{

	int now=0,len=s.length();

	for(int i=0;i<len;i++)

	{

		int ch=s[i]-'a'+1;

		if(!tire[now].zi[ch])	return false;

		now=tire[now].zi[ch];

	}

	return true;

}

巴特西

KMP+Tire树(模板)

最新文章

热门文章