我们考虑如何每一个字符串用唯一的方式表示。
不难想到可以将该字符串分成一个最长的前缀和一个后缀。
我们将所有字符串插入 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; }
|