题目链接：HDU-5129
题目大意为给一堆字符串，问由任意两个字符串的前缀子串（注意断句）能组成多少种不同的字符串。
思路是先用总方案数减去重复的方案数。
考虑对于一个字符串S，如图，假设S1，S2，S3，S4，S5，S6均为前缀。
换言之，对于这种字符串，我们计算了三次。
发现，重复的方案数，等于中间如图有颜色的方块的数量。所以我们要做的也就是计数像图中有颜色的小方块的数量。
我们可以通过遍历像S6一样的字符串的数量，来计算重复的方案数。S6满足以下条件：
- 存在一个前缀S4为S6的后缀，且S4为S6的最长的“是前缀的”后缀（保证是小方块间没有隔板）。
- S6-S4为某个前缀的后缀（在图中为S3的后缀）。
我们发现，对于某一个S6，其对应的S4时一定的。
我们用sum[S]表示以S为后缀的前缀字符串的数量。
这样，当我们遍历S6，对于每一个S6，我们找到其对应的S4后，只要减去（ sum[S6-S4] - 1 ）即可。
所以我们要处理的，就是以下两个问题：
- 如何找到S6对应的S4
- 如何求sum[S]
这时候，我们发现S6与S4的关系，和AC自动机的性质很像。S6在失配时跳到的位置就是S4。于是第一个问题解决了。
对于第二个问题，我们同样可以通过AC自动机找到。具体的参见代码。
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std; typedef long long LL;
const LL MAXN=;
const LL SIGMA_SIZE=;
struct Trie
{
LL ch[MAXN][SIGMA_SIZE];
LL fa[MAXN];
LL sz; //节点总数
Trie() { sz=; fa[]=-; memset(ch[],,sizeof(ch[])); }
LL idx(char c) { return c-'a'; } //节点c的编号
void clear() { sz=; fa[]=-; memset(ch[],,sizeof(ch[])); } //在Trie中插入字符串s
void insert(char *s)
{
LL u=,n=strlen(s);
for(LL i=;i<n;i++)
{
LL c=idx(s[i]);
if(!ch[u][c]) //节点不存在
{
memset(ch[sz],,sizeof(ch[sz]));
fa[sz]=u;
ch[u][c]=sz++; //新建节点
}
u=ch[u][c]; //往下走
}
} //AC自动机部分
LL f[MAXN];
LL deg[MAXN];
LL sum[MAXN]; //sum[i]表示以Si为后缀的前缀的数量
void getFail()
{
queue<LL> q;
f[]=;
//初始化队列
for(LL c=;c<SIGMA_SIZE;c++)
{
LL u=ch[][c];
if(u) { f[u]=; q.push(u); }
}
//按BFS顺序计算失配函数
while(!q.empty())
{
LL r=q.front(); q.pop();
for(LL c=;c<SIGMA_SIZE;c++)
{
LL u=ch[r][c];
if(!u) { ch[r][c]=ch[f[r]][c]; continue; }
q.push(u);
LL v=f[r];
f[u]=ch[v][c];
}
}
for(LL i=;i<sz;i++) { deg[i]=; sum[i]=; }
for(LL i=;i<sz;i++) deg[f[i]]++;
queue<LL> Q;
for(LL i=;i<sz;i++) if(!deg[i]) Q.push(i);
while(!Q.empty())
{
LL u=Q.front(); Q.pop();
sum[f[u]]+=sum[u];
deg[f[u]]--;
if(!deg[f[u]]) Q.push(f[u]);
}
} void solve()
{
LL tot=;
for(LL i=;i<sz;i++) if(f[i])
{
LL j=f[i];
LL p=i;
while(j)
{
p=fa[p];
j=fa[j];
}
tot+=sum[p]-;
}
printf("%lld\n",1LL*(sz-)*(sz-)-tot);
}
};
Trie T;
int main()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif
LL n;
while(scanf("%lld",&n) && n)
{
scanf("%lld",&n);
for(LL i=;i<=n;i++)
{
char s[];
scanf("%s",s);
T.insert(s);
}
T.getFail();
T.solve();
T.clear();
}
return ;
}