求这道题 AC 自动机做法

#include <iostream>
using namespace std;
const int N = 200010;
int idle = 1;
int tr[N][26] = { 0 };
char str[N][15];
int cnt[N] = { 0 };
int fa[N];
void insert(int i) {
    int p = 0;
    for (int j = 1; str[i][j]; j++) {
        int ch = str[i][j] - 'a';
        if (!tr[p][ch]) tr[p][ch] = idle++;
        fa[tr[p][ch]] = p;
		p = tr[p][ch];
    }
    cnt[p]++;    
}
int q[N], nex[N] = { 0 };
void build() {
	int hh = 1, tt = 1;
	for (int i = 0; i < 26; i++)
		if (tr[0][i])
			q[tt++] = tr[0][i];
	while (hh != tt) {
		int fat = q[hh++];
		for (int i = 0; i < 26; i++) {
			int j = tr[fat][i];
			if (j) nex[j] = tr[nex[fat]][i], q[tt++] = j;
			else tr[fat][i] = tr[nex[fat]][i];
		}
	}
}
bool mark[N] = { 0 };
/*计算每个节点能够到达的模式串数
 在样例 3 中，这种计数方式会重复计算，不知道如何修改 
 */
void dfs(int u) {
	if (mark[u]) return ;
	mark[u] = true;
	dfs(fa[u]);
	cnt[u] += cnt[fa[u]];
	dfs(nex[u]);
	cnt[u] += cnt[nex[u]];
} 
int get_cnt(int i) {
	int p = 0;
	for (int j = 1; str[i][j]; j++) {
		int ch = str[i][j] - 'a';
		p = tr[p][ch];
	} 
	return cnt[p] - 1;
}
#define ll long long
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", str[i] + 1);
        insert(i);
    }
    build();
    for (int i = 1; i < idle; i++) dfs(i);
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    	ans += get_cnt(i);
    printf("%lld", ans);
    return 0;
}