【算法】splay
【题解】对于每个结点维护其子树串的hash值，前面为高位，后面为低位。
sum[x]=sum[L]*base[s[R]+1]+A[x]*base[s[R]]+sum[R]，其中sum为哈希，base为乘权，A为数值(即字符)。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100010,inf=0x3f3f3f3f,bases=233; int f[maxn],t[maxn][2],s[maxn],A[maxn],a[maxn],sz=0,root,n; unsigned long long sum[maxn],a_,b_,b[maxn]; int Node(int fa,int num) { sz++; f[sz]=fa;t[sz][0]=t[sz][1]=0; s[sz]=1;A[sz]=sum[sz]=num; return sz; } void count(int x) { s[x]=s[t[x][0]]+1+s[t[x][1]]; sum[x]=sum[t[x][0]]*b[s[t[x][1]]+1]+1ull*A[x]*b[s[t[x][1]]]+sum[t[x][1]]; } void build(int fa,int &x,int l,int r) { if(l>r)return; int mid=(l+r)>>1; x=Node(fa,a[mid]); build(x,t[x][0],l,mid-1); build(x,t[x][1],mid+1,r); count(x); } void rotate(int x) { int k=x==t[f[x]][1]; int y=f[x]; t[y][k]=t[x][!k];f[t[x][!k]]=y; if(f[y])t[f[y]][y==t[f[y]][1]]=x;f[x]=f[y];f[y]=x; t[x][!k]=y; sum[x]=sum[y];s[x]=s[y]; count(y); } void splay(int x,int r) { for(int fa=f[r];f[x]!=fa;) { if(f[f[x]]==fa){rotate(x);return;} int X=x==t[x][1],Y=f[x]==t[f[f[x]]][1]; if(X^Y)rotate(x),rotate(x); else rotate(f[x]),rotate(x); } } void find(int &x,int k) { for(int i=x;i;) { if(k<=s[t[i][0]]){i=t[i][0];continue;} if(k==s[t[i][0]]+1){splay(i,x);x=i;return;} k-=s[t[i][0]]+1;i=t[i][1]; } } bool work(int x,int y,int longs) { if(x+longs-1>n||y+longs-1>n)return 0; find(root,x);find(t[root][1],longs+1); a_=sum[t[t[root][1]][0]]; find(root,y);find(t[root][1],longs+1); b_=sum[t[t[root][1]][0]]; if(a_==b_)return 1; return 0; } void ask() { int x,y; scanf("%d%d",&x,&y); int l=0,r=maxn; while(l<r) { int mid=(l+r)>>1; if(work(x,y,mid))l=mid+1; else r=mid; } printf("%d ",l-1); } void repair() { int x;char c; scanf("%d %c",&x,&c); find(root,x+1); A[root]=c-'a'+1; count(root); } void insert() { n++; int x;char c; scanf("%d %c",&x,&c); find(root,x+1);find(t[root][1],1); int y=Node(t[root][1],c-'a'+1); t[t[root][1]][0]=y; f[y]=t[root][1]; count(t[root][1]); count(root); } char str[maxn]; int main() { scanf("%s",str+1); n=strlen(str+1); for(int i=1;i<=n;i++)a[i]=str[i]-'a'+1; b[0]=1; for(int i=1;i<=maxn;i++)b[i]=b[i-1]*bases; root=a[0]=a[n+1]=0; build(0,root,0,n+1); int m; scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%s",str);//不要用%c会读空格，用%s读到空格会停。 if(str[0]=='Q')ask(); if(str[0]=='R')repair(); if(str[0]=='I')insert(); } return 0; }
update：现在已改用fhq-treap代替splay。