【题意】
对一个字符串实现三种操作
Q i j:询问该字符串的后缀i和后缀j的最长公共前缀长度
R i c:将当前字符串第i位变为小写字母c
I i c:在当前字符串第i位后插入一个小写字母c
【输入】
输入文件第一行为一个字符串(仅包含小写字母)。
接下来的一行的整数Q 代表操作的个数(1 ≤Q ≤15000)。
接下来Q 行表示了待执行的操作。
Q i j 表示求LCP(i, j)的数值
R i char 表示将第i 位置的字符替换成小写字母char
I i char 表示在第i 个字符后插入小写字母char
【输出】
对于每一个Q i j,输出一行为LCP(i, j)的数值。
最初看到这道题在想是不是对于修改可以通过修改后缀数组实现
发现不可行
ac做法是hash
求最长公共前缀可以通过二分答案来变为存在性问题
那么只要比较二者的hash值即可
虽然有一定概率不同的字符串hash为相同的值,但是只要方程选取的当出错的几率还是很小的
那么问题就转换为了如何快速求一个字符串子串的hash值
采用的hash方程为长度为n的字符串的hash值为(a[1]*k^0+a[2]*k^1+a[3]*k^2..+a[n]*k^(n-1)) mod maxn
如果用这个方程的话,那么一段的hash可以通过两段直通末尾的字符串hash值相减得出
我才用了splay树来维护快速查询
对于每个字符将其放入树中,其左子树中的字符都是比其位置靠前的,其右子树中的字符都是比其位置靠后的
每个节点的权值h为其子树(包括本身)构成的原字符串的子串的hash值,并记录子树的节点总数sum
那么询问原字符串一个后缀的hash值只需要将他所在的节点上移到根节点处,这时他(它本身代表的字符序号+(其右子树权值*k))即为这个后缀的hash值
对于变换,只要将改变的节点移到根节点之后修改hash值即可
对于插入,将要插入位置的前一个移到根节点后插到右子树即可
splay我不太喜欢,因为不是稳定结构,据说可以用块状链表来做,想了想似乎是可以的,将原字符串分为根号n段?具体做法不太清楚。
{$inline on} program prefix; const maxn=9875321; k=27; var tot,count,a,b,ans,q,n,i,j:longint; s:ansistring; ch,order,space:char; h:array [0..100011] of int64; power:array [0..100011] of int64; nam,father,left,right,sum:array [0..200011] of longint; procedure update (now:longint);inline; begin h[now]:=(h[left[now]]+power[sum[left[now]]]*nam[now] +power[sum[left[now]]+1]*h[right[now]]) mod maxn; end; procedure build (l,r,mother:longint); var now:longint; begin if l>r then exit; now:=(l+r) div 2; nam[now]:=ord(s[now])-96; sum[now]:=r-l+1; if now>mother then right[mother]:=now else left[mother]:=now; father[now]:=mother; build(l,now-1,now); build(now+1,r,now); update(now); end; function find (lef,now:longint):longint; begin if sum[left[now]]+1=lef then exit(now) else if sum[left[now]]+1<lef then exit(find(lef-(sum[left[now]]+1),right[now])) else exit(find(lef,left[now])); end; procedure rotate (son,mother:longint); begin father[son]:=father[mother]; father[mother]:=son; if left[father[son]]=mother then left[father[son]]:=son else right[father[son]]:=son; if left[mother]=son then begin left[mother]:=right[son]; father[right[son]]:=mother; right[son]:=mother; end else begin right[mother]:=left[son]; father[left[son]]:=mother; left[son]:=mother; end; sum[son]:=sum[mother]; sum[mother]:=sum[left[mother]]+sum[right[mother]]+1; update(mother); update(son); end; procedure rep (who:longint;what:char); var i:longint; begin i:=find(who,right[0]); while father[i]<>0 do rotate(i,father[i]); nam[i]:=ord(what)-96; update(i); end; procedure ins (who:longint;what:char); var i:longint; begin i:=find(who,right[0]); while father[i]<>0 do rotate(i,father[i]); inc(n); nam[n]:=ord(what)-96; right[n]:=right[i]; father[right[i]]:=n; father[n]:=i; right[i]:=n; inc(sum[i]); sum[n]:=sum[right[n]]+1; update(n); update(i); end; function hash (a,b:longint):longint; var i,j:int64; begin i:=find(a,right[0]); while father[i]<>0 do rotate(i,father[i]); i:=nam[i]+k*h[right[i]]; if b>n then j:=0 else begin j:=find(b,right[0]); while father[j]<>0 do rotate(j,father[j]); j:=nam[j]+k*h[right[j]]; end; exit(((i-j*power[b-a] mod maxn) mod maxn + maxn) mod maxn); end; function lcq (a,b:longint):longint; var i,j,l,r,mid:longint; begin if nam[find(a,right[0])]<>nam[find(b,right[0])] then exit(0); l:=1; if n-a+1<n-b+1 then r:=n-a+1 else r:=n-b+1; while l<>r do begin mid:=l+r-(l+r) div 2; if hash(a,a+mid)=hash(b,b+mid) then l:=mid else r:=mid-1; end; exit(l); end; begin assign(input,'prefix.in'); reset(input); assign(output,'prefix.out'); rewrite(output); readln(s); n:=length(s); power[0]:=1; for i:=1 to 100010 do power[i]:=power[i-1]*k mod maxn; build(1,n,0); readln(q); for i:=1 to q do begin read(order); case order of 'Q':begin read(a,b); writeln(lcq(a,b)); end; 'R':begin read(a,space,ch); rep(a,ch); end; 'I':begin read(a,space,ch); ins(a,ch); end; end; readln; end; close(input); close(output); end.