标签：Splay+Hash

题解：

　　首先肯定不是后缀数组，当然splay比后缀数组要简单一些。

　　求解这个问题，我们可以二分，对于两个串A，B他们的最长公共前缀是可以二分出来的。

　　那么我们对于每一个后缀，二分一下，但是需要维护这一个东西，那么我们使用splay来维护序列。按照下标为关键字来把初始字符串构造成一棵splay，然后维护一个Hash值代表子树的字符串的Hash值。每次将L-1旋转到根，再把R+1旋转到根的右儿子，这样就可以查询一段区间的Hash值了。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #define LL long long  6 using namespace std;  7 const int MAXN=160000,mod=192608173;  8 char s[MAXN];  9 int n,m,root,CNT; 10 int v[MAXN]; 11 int sz[MAXN],fa[MAXN],ha[MAXN],val[MAXN],ch[MAXN][2]; 12 void Update(int x) 13 { 14   int ls=ch[x][0],rs=ch[x][1]; 15   sz[x]=sz[ls]+sz[rs]+1; 16   ha[x]=ha[ls]+(LL)val[x]*v[sz[ls]]%mod+(LL)ha[rs]*v[sz[ls]+1]%mod; 17   ha[x]%=mod; 18 } 19 void Rotate(int x,int &y) 20 { 21   int old=fa[x],oldf=fa[old],op=ch[old][1]==x; 22   if(old==y) y=x; 23   else ch[oldf][ch[oldf][1]==old]=x; 24   fa[x]=oldf; 25   fa[ch[x][op^1]]=old; ch[old][op]=ch[x][op^1]; 26   fa[old]=x; ch[x][op^1]=old; 27   Update(old); Update(x); 28 } 29 void Splay(int x,int &y) 30 { 31   int old,oldf; 32   while(x!=y) 33     { 34       old=fa[x]; oldf=fa[old]; 35       if(old!=y){ 36         if((ch[old][0]==x)^(ch[oldf][0]==old)) Rotate(x,y); 37         else Rotate(old,y); 38       } 39       Rotate(x,y); 40     } 41 } 42 void Build(int &x,int ll,int rr,int FA) 43 { 44   x=++CNT; int mid=(ll+rr)/2; 45   fa[x]=FA; val[x]=s[mid]-'a'+1; 46   if(ll
         
          mid)Build(ch[x][1],mid+1,rr,x); 48   Update(x); 49 } 50 int find(int x) 51 { 52   int now=root; 53   while(1) 54     { 55       if(x<=sz[ch[now][0]]) now=ch[now][0]; 56       else 57         { 58           int tmp=sz[ch[now][0]]+1; 59           if(x<=tmp) return now; 60           x-=tmp; now=ch[now][1]; 61         } 62     } 63 } 64 int Query(int ll,int rr) 65 { 66   int x=find(ll-1),y=find(rr+1); 67   Splay(x,root); Splay(y,ch[root][1]); 68   return ha[ch[y][0]]; 69 } 70 int work(int x,int y) 71 { 72   int L=1,R=n-y,mid,res=0; 73   while(L<=R) 74     { 75       mid=(L+R)/2; 76       if(Query(x,x+mid-1)==Query(y,y+mid-1)) L=mid+1 ,res=mid; 77       else R=mid-1; 78     } 79   return res; 80 } 81 void Insert(int x,int V) 82 { 83   int y=x+1; n++; 84   x=find(x); y=find(y); 85   Splay(x,root); Splay(y,ch[root][1]); 86   CNT++; val[CNT]=V; 87   fa[CNT]=y; ch[y][0]=CNT; 88   Update(CNT); Update(y); Update(root); 89 } 90 int main() 91 { 92   scanf("%s",s+2); s[1]='a'-1; 93   n=strlen(s+1)+1; s[n]='a'-1; 94   scanf("%d",&m); v[0]=1; 95   for(int i=1;i
          
           y) swap(x,y);104 printf("%d\n",work(x+1,y+1));105 }106 else if(s[0]=='R')107 {108 int x; scanf("%d%s",&x,s);109 x=find(x+1); Splay(x,root); 110 val[x]=s[0]-'a'+1; Update(x);111 }112 else if(s[0]=='I')113 {114 int x; scanf("%d%s",&x,s); 115 Insert(x+1,s[0]-'a'+1);116 }117 }118 }