题面在这里
题意：
给n个单词，问每个单词在所有单词中出现了多少次。
做法：
后缀数组。（ac自动机也可以qwq） 首先把所有串用不同的字符拼接起来，跑大串的sa。 然后对于每一个单词，假设它的长度为len，暴力找到h[i]>=len的最左边和最右边的位置l,r，然后这个单词出现的次数就是这一段的长度r-(l-1)+1。 （其实暴力应该是水过的？qaq，正解大概搞个二分什么的就行。。反正暴力能过qaq。。1000+ms）
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cctype>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long ll;
const int N =
2000000;
int n, m, all;
int rk[N], tp[N], sa[N], h[N], len[
210], tong[N], pos[
210], s[N];
char str[N];
inline void ssort() {
for(
int i =
0; i <= all; i ++) tong[i] =
0;
for(
int i =
1; i <= n; i ++) tong[rk[tp[i]]] ++;
for(
int i =
1; i <= all; i ++) tong[i] += tong[i-
1];
for(
int i = n; i >=
1; i --) sa[tong[rk[tp[i]]] --] = tp[i];
}
inline void get_sa() {
for(
int i =
1; i <= n; i ++) rk[i] = s[i], tp[i] = i;
all =
500; ssort(); all =
1;
int w =
1;
while(all < n) {
int t =
0;
for(
int i = n-w+
1; i <= n; i ++) tp[++ t] = i;
for(
int i =
1; i <= n; i ++)
if(sa[i] > w) tp[++ t] = sa[i]-w;
ssort();
for(
int i =
1; i <= n; i ++) tp[i] = rk[i];
rk[sa[
1]] = all =
1;
for(
int i =
2; i <= n; i ++)
rk[sa[i]] = (tp[sa[i]] == tp[sa[i-
1]] && tp[sa[i]+w] == tp[sa[i-
1]+w])?all:++ all;
w <<=
1;
}
int k =
0;
for(
int i =
1; i <= n; i ++) {
if(k) k --;
int j = sa[rk[i]-
1];
for(; i+k <= n && j+k <= n && s[i+k] == s[j+k]; k ++);
h[rk[i]] = k;
}
}
int main() {
scanf(
"%d", &m);
for(
int i =
1; i <= m; i ++) {
scanf(
"%s", str); len[i] =
strlen(str); pos[i] = n+
1;
for(
int j =
0; j < len[i]; j ++) s[++ n] = str[j];
s[++ n] =
'z'+i;
}
get_sa();
for(
int i =
1; i <= m; i ++) {
int x = rk[pos[i]], j, lft, rgt; j = x;
while(j && h[j] >= len[i]) j --;
lft = j+
1; j = x+
1;
while(j <= n && h[j] >= len[i]) j ++;
rgt = j-
1;
printf(
"%d\n", rgt-(lft-
1)+
1);
}
return 0;
}
