COCI2013-2014 Contest#1 F SLASTIČAR
其实挺妙的一个数据结构题
题意: 给定一个A串，对于查询的每个(B)串，从头开始匹配匹配(A)的每个后缀，每次匹配失败的代价是( ext{LCP}+1)可，匹配成功的代价是(|B|)，且立即停止，求代价总和
设(A)串长为(n)，查询个数为(q)，查询总长为(m)
我们知道求两个串的( ext{LCP})可以把两个串中间放一个符号分开，跑后缀数组/后缀自动机
但是首先是(m=3cdot 10^6)，内存就开不下
而且发现，如果(|B|)的某个前缀未出现在(A)中，后面的部分都不造成贡献，所以可以在(A)串中定位(B)的每个前缀
这样就只需要求(A)的后缀数组即可，然而，这个并不好实现
假设当前已经定位了一个长度为(i)的前缀，其对应的合法后缀排名范围为([L_i,R_i])
那么接下来就是在当前前缀上接上下一个字符(c)，这个如果再外加数据结构并不好实现
考虑后缀数组的性质，([L_i,R_i])这些后缀前(d)个字符相同，(d+1)个字符呈单调非递减
所以字符(c)出现的范围也一定是一段区间，可以直接两次二分得到
这样查询([L_i,R_i])的复杂度为(log n)，这样就用(O(mlog n))的复杂度完成了串定位
如果不考虑每次完成匹配后停止，其实答案就是(sum R_i-L_i+1)，即(sum_i LCP_i=sum_i sum_j [LCP_jge i])
设最终的匹配位置为(p)，这个位置可以用线段树在最后的一段([L_{|B|},R_{|B|}])中求最小值得到
考虑减掉多余的部分，即减去实际位置(>p)的且在后缀数组排名在([L_i,R_i])中的部分
可以把所有的([L_i,R_i])拿出来作为，离线询问，用树状数组维护查询，复杂度为(O((n+m)log n))
因此总复杂度为(O((n+m)log n))
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> Pii;
#define reg register
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,const T &b){ ((a<b)&&(a=b)); }
const int N=1e5+10,M=3e6+10;
int n,m;
char s[N],t[N];
int rk[N<<1],tmp[N],cnt[N],sa[N];
void Build(int n){
rep(i,1,n) cnt[int(s[i])]++;
rep(i,1,200) cnt[i]+=cnt[i-1];
rep(i,1,n) rk[i]=cnt[(int)s[i]],sa[i]=i;
for(reg int k=1;k<n;k<<=1) {
for(reg int i=0;i<=n;++i) cnt[i]=0;
for(reg int i=1;i<=n;++i) cnt[rk[i+k]]++;
for(reg int i=1;i<=n;++i) cnt[i]+=cnt[i-1];
for(reg int i=n;i>=1;--i) tmp[cnt[rk[i+k]]--]=i;
for(reg int i=0;i<=n;++i) cnt[i]=0;
for(reg int i=1;i<=n;++i) cnt[rk[i]]++;
for(reg int i=1;i<=n;++i) cnt[i]+=cnt[i-1];
for(reg int i=n;i>=1;--i) sa[cnt[rk[tmp[i]]]--]=tmp[i];
for(reg int i=1;i<=n;++i) tmp[sa[i]]=tmp[sa[i-1]]+(rk[sa[i]]!=rk[sa[i-1]]||rk[sa[i]+k]!=rk[sa[i-1]+k]);
for(reg int i=1;i<=n;++i) rk[i]=tmp[i];
}
}
void FindChar(int &l,int &r,int len,int c){
int tl=l,tr=r;
int lres=-1,rres=-1;
while(l<=r){
int mid=(l+r)>>1;
if(s[sa[mid]+len]<=c) l=mid+1,lres=mid;
else r=mid-1;
}
if(lres==-1 || s[sa[lres]+len]!=c) { l=0; return; }
l=tl,r=tr;
while(l<=r){
int mid=(l+r)>>1;
if(s[sa[mid]+len]>=c) r=mid-1,rres=mid;
else l=mid+1;
}
l=rres,r=lres;
}
ll ans[N];
int ql[M],qr[M],qid[M],qnxt[M];
int head[N],qc;
int L[N],R[N];
struct BIT{
int s[N];
void Add(int p) { while(p<=n) s[p]++,p+=p&-p; }
int Que(int p) {
int res=0;
while(p) res+=s[p],p-=p&-p;
return res;
}
int Que(int l,int r){ return Que(r)-Que(l-1); }
} T;
struct Tree{
int s[N<<2];
void Build(int p,int l,int r){
if(l==r) { s[p]=sa[l]; return ;}
int mid=(l+r)>>1;
Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
s[p]=min(s[p<<1],s[p<<1|1]);
}
int Que(int p,int l,int r,int ql,int qr){
if(ql<=l && r<=qr) return s[p];
int mid=(l+r)>>1,res=1e9;
if(ql<=mid) cmin(res,Que(p<<1,l,mid,ql,qr));
if(qr>mid) cmin(res,Que(p<<1|1,mid+1,r,ql,qr));
return res;
}
}SGT;
int main(){
scanf("%d%s",&n,s+1);
Build(n),scanf("%d",&m);
SGT.Build(1,1,n);
rep(i,1,m) {
scanf("%s",t+1);
L[0]=1,R[0]=n;
int len=0,pos=1;
for(int j=1;t[j];++j) {
L[len=j]=L[j-1],R[j]=R[j-1];
FindChar(L[j],R[j],j-1,t[j]);
if(!L[j]){ pos=0; break; }
ans[i]+=R[j]-L[j]+1;
}
if(pos && (pos=SGT.Que(1,1,n,L[len],R[len]))<n) {
ans[i]+=pos-1,pos++;
rep(j,1,len){
qc++,ql[qc]=L[j],qr[qc]=R[j],qid[qc]=i,qnxt[qc]=head[pos];
head[pos]=qc;
}
} else ans[i]+=n;
}
drep(i,n,1){
T.Add(rk[i]);
for(int j=head[i];j;j=qnxt[j]) ans[qid[j]]-=T.Que(ql[j],qr[j]);
}
rep(i,1,m) printf("%lld
",ans[i]);
}