COCI2013-2014 Contest#1 F SLASTIČAR

其实挺妙的一个数据结构题

题意: 给定一个A串，对于查询的每个$B$串，从头开始匹配匹配$A$的每个后缀，每次匹配失败的代价是$\text{LCP}+1$可，匹配成功的代价是$|B|$，且立即停止，求代价总和

设$A$串长为$n$，查询个数为$q$，查询总长为$m$

我们知道求两个串的$\text{LCP}$可以把两个串中间放一个符号分开，跑后缀数组/后缀自动机

但是首先是$m=3\cdot 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(m\log n)$的复杂度完成了串定位

如果不考虑每次完成匹配后停止，其实答案就是$\sum R_i-L_i+1$，即$\sum_i LCP_i=\sum_i \sum_j [LCP_j\ge 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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#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\n",ans[i]);
}