失配树
cpp
void solve(){
string s;
cin>>s;
int n=s.size();
s=" "+s;
vector<int> ne(n+1),dep(n+1);
vector par(n+1,vector<int>(25));
par[1][0]=0;
dep[1]=1;
for(int i=2,j=0;i<=n;i++){
while(j&&s[i]!=s[j+1])j=ne[j];
if(s[i]==s[j+1])j++;
ne[i]=j;
dep[i]=dep[j]+1;
par[i][0]=j;
}
for(int j=1;j<22;j++){
for(int i=1;i<=n;i++)par[i][j]=par[par[i][j-1]][j-1];
}
int m;
cin>>m;
while(m--){
int u,v;
cin>>u>>v;
if(dep[u]<dep[v])swap(u,v);
while(dep[u]>dep[v])u=par[u][__lg(dep[u]-dep[v])];
if(u==v){
cout<<ne[u]<<"\n";
continue;
}
for(int i=__lg(dep[u]);i>=0;i--){
if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
}
cout<<par[u][0]<<"\n";
}
}