学习笔记：kmp&失配树

1.kmp

这就不讲了吧，border数组弄懂就是水算法了！但是变种真的毒瘤啊

2.hash

emmmmm

3.fail树

这就是kmp的border数组的变种

kmp一次一次next跳，太慢了！

我们就想到倍增优化嘛

\(n\)个点，\(n-1\) 条边 联通

一眼顶针这就是一颗树

那么找共同前缀就是找LCA

倍增啥的搞搞就得

传送：here

Code:

#include<bits/stdc++.h>
#define ll long long
#define MAXN 1000005
using namespace std;
int n,g;
int nxt[MAXN];
int f[MAXN][24],dep[MAXN];
string s;
void get(string s)
{
	int i=0,j=-1;
	nxt[0]=-1;
	while(i<=s.size())
	{
		if(j==-1||s[i]==s[j])
			nxt[++i]=++j;
		else 
			j=nxt[j];
	}
}
int lca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=20;i>=0;i--)
		if(dep[f[u][i]]>=dep[v]) u=f[u][i];
	for(int i=20;i>=0;i--)
		if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
	if(u==v) return u;
	return f[u][0]; 
}
int main()
{ 
	ios::sync_with_stdio(false);	
	cin.tie(0);
	cout.tie(0); 
	cin>>s;
	get(s);
	for(int i=1;i<=s.size();i++)
	{
		f[i][0]=nxt[i];
		dep[i]=dep[nxt[i]]+1;
//		cout<<dep[i]<<" ";
		for(int j=1;f[i][j-1];j++)
			f[i][j]=f[f[i][j-1]][j-1];
	}
	cin>>g;
	while(g--)
	{
		int u,v;
		cin>>u>>v;
		cout<<lca(nxt[u],nxt[v])<<"\n";
	}
	return 0;
}

今天的算法真是通俗