链接
https://ac.nowcoder.com/acm/contest/5667/A
题意
有 $n$ 个字符串
定义 $f(s,t)$ 为最大的 $i$ 满足 $s_{1…i}=t_{|t|-i+1…|t|}$
求 $\sum_{i=1}^n\sum_{j=1}^n{f(s_i,s_j)^2}\pmod{998244353}$
思路
将每一个后缀 Hash ，再遍历每个字符串的前缀找相同的后缀的个数
但有可能找到的后缀来自同一个字符串，又因为这些后缀都是当前字符串的前缀，所以我们可以用 KMP 算法算出 next 数组找出当前位置的最大 border，从前往后执行 cnt[next[i+1]-1]-=cnt[i] 即可完成去重
最后计算答案即可
代码
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=1e6+5;
const long long MOD=998244353;
const long long HASH_BASE=131;
const long long HASH_MOD[2]={1000173169,1000000007};
string s[N];
long long power[M][2],ha[M][2],res[M],ans;
int nxt[M];
map<pair<long long,long long>,int>mp;
void init() {
power[0][0]=power[0][1]=1;
for(int i=1;i<M;i++)
for(int j=0;j<2;j++) {
power[i][j]=power[i-1][j]*HASH_BASE%HASH_MOD[j];
}
}
void init_hash(string &s) {
int len=s.length();
ha[len][0]=ha[len][1]=0;
for(int i=len-1;i>=0;i--) {
for(int j=0;j<2;j++)
ha[i][j]=(s[i]*power[len-i-1][j]%HASH_MOD[j]+ha[i+1][j])%HASH_MOD[j];
mp[make_pair(ha[i][0],ha[i][1])]++;
}
}
void kmp(string &s) {
int len=s.length();
int i=0,j=-1;
nxt[0]=-1;
while(i<len) {
if(j==-1||s[i]==s[j]) i++,j++,nxt[i]=j;
else j=nxt[j];
}
}
void cal(string &s) {
int len=s.length();
for(int i=0;i<len;i++) {
for(int j=0;j<2;j++) {
if(i==0) ha[i][j]=s[i];
else ha[i][j]=(ha[i-1][j]*HASH_BASE%HASH_MOD[j]+s[i])%HASH_MOD[j];
}
res[i]=mp[make_pair(ha[i][0],ha[i][1])];
}
kmp(s);
for(int i=0;i<len;i++) if(nxt[i+1]>0) res[nxt[i+1]-1]-=res[i];
for(int i=0;i<len;i++) if(res[i]>0) ans=(ans+1ll*(i+1)*res[i]%MOD*(i+1)%MOD)%MOD;
}
int main() {
init();
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
cin>>s[i];
init_hash(s[i]);
}
for(int i=1;i<=n;i++) cal(s[i]);
printf("%lld\n",ans);
return 0;
}
|