我们考虑如何每一个字符串用唯一的方式表示。
不难想到可以将该字符串分成一个最长的前缀和一个后缀。
我们将所有字符串插入 Trie 树中，枚举每一个前缀，若当前前缀没有 $t$ 这个儿子，那么其在后接一个 $t$ 开头的后缀的魔咒中是最长前缀，可以更新答案。
故我们还需要维护以 $t$ 开头的后缀数量，可以将字符串倒序插入 Trie 树。
对于一个前缀，若有 $t$ 这个孩子，我们仍然可以找一个为 $t$ 的长度为 $1$ 的后缀接上，也需要更新答案。
对于长度为 $1$ 的在书本上的魔咒，上面统计不到，也需要更新答案。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e6;
int n;
char s[45];
int rt1,rt2;
int ch[maxn+5][30],tot;
int cnt[30];
bool flg[30],vis[30];
ll ans;
void Dfs(int u){
for(int t=0;t<26;t++){
if(ch[u][t]){
if(flg[t]) ans++;
Dfs(ch[u][t]);
}
else ans+=cnt[t];
}
}
signed main(){
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
rt1=++tot,rt2=++tot;
scanf("%d",&n);
while(n--){
scanf("%s",s);
int len=strlen(s);
flg[s[len-1]-'a']=1;
if(len==1&&!vis[s[0]-'a'])
vis[s[0]-'a']=1,ans++;
for(int i=0,u=rt1;i<len;i++){
int t=s[i]-'a';
if(!ch[u][t]) ch[u][t]=++tot;
u=ch[u][t];
}
for(int i=len-1,u=rt2;i>=0;i--){
int t=s[i]-'a';
if(!ch[u][t]) ch[u][t]=++tot,cnt[t]++;
u=ch[u][t];
}
}
for(int i=0;i<26;i++)
if(ch[rt1][i]) Dfs(ch[rt1][i]);
printf("%lld",ans);
return 0;
}
|