「TJOI2013」单词-后缀数组+二分

可读版题意:

给定$n$个字符串,第$i$个字符串的长度为$M_i$,求每个字符串在所有字符串中出现的次数。

数据范围:$n \leq 100, M = \sum M_i \leq 10^6$.


原题面:

小张最近在忙毕设,所以一直在读论文。一篇论文是由许多单词组成但小张发现一个单词会在论文中出现很多次,他想知道每个单词分别在论文中出现了多少次。

链接

Luogu P3966

题解

首先我们加不同的分隔符,将所有字符串拼成一个整串。

注意到这个问题,其实可以转化为若干个子串在母串中的出现次数。

套路题吧…找到这个子串出现位置的后缀在$ht$数组里面的位置,往两侧延伸(这个地方二分答案),看最多的$ht \geq len$的范围,这个区间里面的所有串都是出现的位置。然后计算一下长度就可以得到答案。

时间复杂度$O(M \log {M} + n \log{M})$。

开始写了一个$O(NM)$的暴力死活过不去,还以为自己常数大…233

代码

点击切换显示状态
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 <cstdio>
#include <algorithm>
#include <cstring>
#include <unistd.h>
#include <cctype>
#include <cmath>
using namespace std;

const int MAXN = 1001000,logn = 21,MAXM = 300;

namespace SA{
int s[MAXN],sa[MAXN],rk[MAXN],x[MAXN],y[MAXN],ht[MAXN];
int cnt[MAXN];
void get_SA(int n,int m){
for(int i = 0;i<m;i++) cnt[i] = 0;
for(int i = 0;i<n;i++) cnt[s[i]]++;
for(int i = 1;i<m;i++) cnt[i] += cnt[i-1];
for(int i = n-1;~i;--i) sa[--cnt[s[i]]] = i;
m = rk[sa[0]] = 0;
for(int i = 1;i<n;i++) rk[sa[i]] = s[sa[i]] != s[sa[i-1]]?++m:m;
for(int j = 1;;j<<=1){
if(++m == n) break;
for(int i = 0;i<j;i++) y[i] = n-j+i;
for(int i = 0,k = j;i<n;i++) if(sa[i] >= j) y[k++] = sa[i]-j;
for(int i = 0;i<n;i++) x[i] = rk[y[i]];
for(int i = 0;i<m;i++) cnt[i] = 0;
for(int i = 0;i<n;i++) cnt[x[i]]++;
for(int i = 1;i<m;i++) cnt[i] += cnt[i-1];
for(int i = n-1;~i;--i) sa[--cnt[x[i]]] = y[i],y[i] = rk[i];
m = rk[sa[0]] = 0;
for(int i = 1;i<n;i++) rk[sa[i]] = (y[sa[i]]!=y[sa[i-1]] || y[sa[i]+j]!=y[sa[i-1]+j])?++m:m;
}
}
void getheight(int n){
for(int i = 0,h = ht[0] = 0;i<n;i++){
int j = sa[rk[i]-1];
while(i+h<n&&j+h<n&&s[i+h]==s[j+h]) ++h;
if(ht[rk[i]] = h) --h;
}
}
template <typename T>
void build(int n,const T *str){
int m = 128+200;++n;
for(int i = 0;i<n;i++)
s[i] = str[i];
get_SA(n,m);
getheight(n);
}
}

namespace ST{
int minn[MAXN][logn];
void build(int n,int *num){
int l = log2(n);
for(int i = 0;i<=n;i++)
minn[i][0] = num[i];
for(int j = 1;j<=l;j++){
for(int i = 0;i+(1<<(j-1))<=n;i++){
minn[i][j] = min(minn[i+(1<<(j-1))][j-1],minn[i][j-1]);
}
}
}
int query(int l,int r){
int t = log2(r-l+1);
return min(minn[l][t],minn[r-(1<<t)+1][t]);
}
}

int n,m;

int query(int p,int len){
p = SA::rk[p];
int l,r,b = 0,e = p;
while(b!=e){
int mid = (b+e)>>1;
if(ST::query(mid+1,p)<len)
b = mid+1;
else e = mid;
}
l = b;
b = p+1,e = n;
while(b!=e){
int mid = (b+e)>>1;
if(ST::query(p+1,mid)>=len)
b = mid+1;
else e = mid;
}
r = b;
return r-l;
}

int ans[MAXM];
int b[MAXM],len[MAXM];
int s[MAXN];char t[MAXN];

void init(){
scanf("%d",&m);
for(int i = 1;i<=m;i++){
scanf("%s",t);
len[i] = strlen(t),b[i] = n;
for(int j = 0;j<len[i];j++) s[n++] = t[j];
s[n++] = 127+i;
}
s[n] = 'a' - 1;
SA::build(n,s);
ST::build(n+1,SA::ht);
}

void solve(){
for(int i = 1;i<=m;i++){
printf("%d\n",query(b[i],len[i]));
}
}

int main(){
init();
solve();
return 0;
}