失配树（KMP+LCA）

int f[1000005][23];//j表示第几次大border长度 0就是最大border 1就是次大 以此类推。
int dep[1000026];
void solve() {
    string s;
    cin>>s;
    dep[1]=1;
    for(int i=1,j=0;i<sz(s);i++){
        while(j&&s[i]!=s[j])j=f[j][0];
        j+=(s[i]==s[j]);f[i+1][0]=j;
        dep[i+1]=dep[j]+1;
    }
 //  rep(i,1,sz(s))cout<<f[i][0]<<" ";//既是前缀又是后缀的长度 不包含本身。
    rep(i,1,21){
        for(int j=1;j<=sz(s);j++){
            f[j][i]=f[f[j][i-1]][i-1];
            //cout<<f[3][1]<<" "<<f[2][0];cn;
        }
    }
    //rep(i,1,sz(s))cout<<f[i][1]<<" ";
   // rep(i,1,sz(s))cout<<dep[i]<<" ";//1 2 3 4 1 1 2 1 1 2 3
   //dep表示往前跳几次跳到0
     int m;
     cin>>m;
     while(m--){
         int l,r;
         cin>>l>>r;
         if(dep[l]<dep[r])swap(l,r);
         for(int i=20;i>=0;i--){if(dep[f[l][i]]>=dep[r])l=f[l][i];}
         for(int i=20;i>=0;i--){if(f[l][i]!=f[r][i])l=f[l][i],r=f[r][i];}
         cout<<f[l][0];
         cn;
     }
}

一些define

#define cn cout<<'\n'
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define sz(x) (x).size()