和上一篇题目几乎一样，不过还是这道题良心！bzoj好！poj慢到出*

splay大法好! 两次AC不卡常！

#pragma GCC opitmize("O3")#pragma G++ opitmize("O3")#include
    
     #include
     
      #include
      
       #define N 400010#define LL long long#define son(x) (x==ch[f[x]][1]) using namespace std;LL h[N],bas[N]={
     1};int f[N],ch[N][2],sz[N],v[N];int n,m,cnt=0,rt=0,q;inline int newnode(int k){    ++cnt; h[cnt]=v[cnt]=k; sz[cnt]=1;    return cnt;}inline void ps(int x){
          sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;    h[x]=(h[ch[x][0]]*131+v[x])*bas[sz[ch[x][1]]]+h[ch[x][1]];}inline void rot(int x){
         int p=f[x],g=f[p],d=son(x);    ch[p][d]=ch[x][!d]; f[ch[p][d]]=p;    ch[x][!d]=p; f[p]=x; f[x]=g;    if(g) ch[g][p==ch[g][1]]=x; ps(p); ps(x);}inline void splay(int x,int r=0){
         for(int p;(p=f[x])!=r;rot(x))        if(f[p]!=r && son(x)==son(p)) rot(p);    if(!r) rt=x;}inline int select(int k,int x=rt){
         for(int w;;){
             w=sz[ch[x][0]]+1;        if(w==k) return x;        if(k
       
        =k) x=ch[x][0];        else{
      r+=sz[ch[x][0]]+1; x=ch[x][1]; }    }    return r;}inline int rank(int x){
         int r=sz[ch[x][0]]+1;    for(;x;x=f[x])        if(son(x)) r+=sz[ch[f[x]][0]]+1;    return r;}inline void Llink(int x,int v){
      f[ch[x][0]=v]=x; ps(x); }inline void Rlink(int x,int v){
      f[ch[x][1]=v]=x; ps(x); }inline LL gH(int x,int len){
         splay(select(x-1));    splay(select(x+len),rt);    return h[ch[ch[rt][1]][0]];}char c[100010],o[3];int main(){
         scanf("%s%d",c,&n); m=strlen(c); rt=newnode(0);    for(int i=1;i<100010;++i) bas[i]=bas[i-1]*131;    for(int i=0;i
        
         >1;                if(gH(a,M)==gH(b,M)) l=M;                else r=M-1;            }            printf("%d\n",l);        }    }