【题意】
给定一个数k
在给定两个字符串A,B
求三元组(i,j,k)(表示从A的第i位起和从B的j位起长度为k的字符串相同)的个数
【输入】
多组数据
每组数据第一行为k
接下来两行分别为A、B(长度均不大于100000)
【输出】
对于每组数据,输出一个数,表示三元组的个数
后缀数组应用题之一
后缀数组的用法很经典
将两个字符串之间加一个没出现过的字符连接起来
然后求height
对于B的一个后缀,对应每一个A的后缀若他们的公共前缀长为l,若l大于等于k,则会有l-k+1种三元组
这个统计便是本题的难点
如果枚举A的后缀和B的后缀,那么复杂度为n^2,对于本题明显是不可以的
所以要另寻途径
根据论文的提示要使用单调栈,我想到了一种实现
按rank的顺序,统计每一个B的后缀名次之前的A的后缀有关的三元组数量
然后再统计每一个A的后缀名次之前的B的后缀有关的三元组数量
两者之和便是答案
将问题划分为了两个等价的问题
那么完成每一个问题的时候从左到右扫描,每一个只跟已扫描过的有关
这时候便可以动态维护了
首先,与许多后缀数组题目中类似的,这里存在三元组的后缀们是聚集在一起的
按height可以分组
对于每一组从左到右扫描,则需要维护一个栈和一个值
这个栈是栈内元素与当前元素公共前缀长度递增的一个栈,值是若当前当前后缀之前的三元组个数
根据最长公共前缀的性质,rank越相近,则公共前缀长度越大,所以从左到右扫描的后缀与当前后缀的公共前缀长度是递减的
栈内每个元素表示之前有total个后缀与当前元素公共前缀长度为sim,明显,若当前height小于某些栈内元素的sim,则需要修改这些元素和值
据此调整,每个元素最多进出栈一次,复杂度为O(N)
program poj3415; var n,m,k,i,j,l,tot:longint; a,b,ans:int64; root,temp:ansistring; dl,change,total,now,keep,sa,rank,height:array [-1..200001] of longint; xl:array [0..200001] of record total,sim:longint; end; min:array [0..19,0..200001] of longint; procedure swap (var a,b:longint); var i:longint; begin i:=a; a:=b; b:=i; end; procedure qsort (s,e:longint); var i,j,k:longint; begin if s>=e then exit; i:=s; j:=e; k:=dl[(s+e) div 2]; while i<=j do begin while root[dl[i]]<root[k] do inc(i); while root[dl[j]]>root[k] do dec(j); if i>j then break; swap(dl[i],dl[j]); inc(i); dec(j); end; qsort(s,j); qsort(i,e); end; procedure st; begin for i:=1 to n do min[0,i]:=height[i]; k:=0; while 1 shl k<n do begin for i:=1 to n do if i + (1 shl k)>n then min[k+1,i]:=min[k,i] else if min[k,i]<min[k,i + (1 shl k)] then min[k+1,i]:=min[k,i] else min[k+1,i]:=min[k,i + (1 shl k)]; inc(k); end; end; begin repeat readln(l); if l=0 then break; readln(root); a:=length(root); readln(temp); b:=length(temp); root:=root+' '+temp; n:=a+b+1; m:=a+1; for i:=1 to n do dl[i]:=i; qsort(1,n); k:=1; for i:=1 to n do begin if root[dl[i]]<>root[dl[k]] then k:=i; rank[dl[i]]:=k; end; k:=0; while 1 shl k<n do begin for i:=1 to n do if i+(1 shl k)>n then change[i]:=0 else change[i]:=rank[i+(1 shl k)]; fillchar(total,sizeof(total),0); for i:=1 to n do inc(total[change[i]]); for i:=1 to n do total[i]:=total[i]+total[i-1]; for i:=1 to n do begin dl[total[change[i]-1]+1]:=i; inc(total[change[i]-1]); end; fillchar(total,sizeof(total),0); for i:=1 to n do inc(total[rank[i]]); for i:=2 to n do total[i]:=total[i]+total[i-1]; fillchar(now,sizeof(now),0); fillchar(keep,sizeof(keep),0); for i:=1 to n do begin if now[rank[dl[i]]]<>change[dl[i]] then begin now[rank[dl[i]]]:=change[dl[i]]; total[rank[dl[i]]-1]:=total[rank[dl[i]]-1]+keep[rank[dl[i]]]; keep[rank[dl[i]]]:=0; end; inc(keep[rank[dl[i]]]); rank[dl[i]]:=total[rank[dl[i]]-1]+1; end; inc(k); end; for i:=1 to n do sa[rank[i]]:=i; fillchar(height,sizeof(height),0); for i:=1 to n do begin if rank[i]=1 then continue; k:=height[rank[i-1]]-1; if k<0 then k:=0; while (i+k<=n)and(sa[rank[i]-1]+k<=n) and(root[i+k]=root[sa[rank[i]-1]+k]) do inc(k); height[rank[i]]:=k; end; ans:=0; tot:=0; a:=0; for i:=3 to n do begin if height[i]<l then begin tot:=0; a:=0; continue; end; if sa[i-1]<m then b:=1 else b:=0; while (tot>0)and(height[i]<=xl[tot].sim) do begin b:=b+xl[tot].total; a:=a-(xl[tot].sim-l+1)*xl[tot].total; dec(tot); end; a:=a+(height[i]-l+1)*b; if b<>0 then begin inc(tot); xl[tot].sim:=height[i]; xl[tot].total:=b; end; if sa[i]>m then ans:=ans+a; end; tot:=0; a:=0; for i:=3 to n do begin if height[i]<l then begin tot:=0; a:=0; continue; end; if sa[i-1]>m then b:=1 else b:=0; while (tot>0)and(height[i]<=xl[tot].sim) do begin b:=b+xl[tot].total; a:=a-(xl[tot].sim-l+1)*xl[tot].total; dec(tot); end; a:=a+(height[i]-l+1)*b; if b<>0 then begin inc(tot); xl[tot].sim:=height[i]; xl[tot].total:=b; end; if sa[i]<m then ans:=ans+a; end; writeln(ans); until false; end.