是这样的, 我刚刚把这题写了一次, 然后我建的树的根是1.这玩意会错, 因为fail指针会挂掉

但是我刚刚不知道这个问题, 样例过了我就交了上去, 结果它过了..

接着我去做加强版, 样例过不去(也是因为建树用的根是1), 我用简单版的代码跑了一次, 输出错了, 我觉得很神奇, 就看了一下才发现这个问题。

所以是数据太水还是啥..

错误代码:

#include <bits/stdc++.h>
using namespace std;
char mp[1000005], s[1000005];
int cnt = 1, p[1000005];
int n, vis[1000005];
struct node {
	int son[28], fail;
}ch[1000005];
void build() {
	int u = 1, m = strlen(mp + 1);
	for(int i = 1;i <= m;i++) {
		if(ch[u].son[mp[i] - 'a']) u = ch[u].son[mp[i] - 'a'];
		else {
			ch[u].son[mp[i] - 'a'] = ++ cnt;
			u = cnt;
		}
	}
	p[u] ++;
}
queue<int> Q;
void fail_find() {
	for(int i = 0;i <= 25;i++) {
		if(ch[1].son[i]) {
			ch[ch[1].son[i]].fail = 1;
			Q.push(ch[1].son[i]);
		}
	}
	while(!Q.empty()) {
		int u = Q.front();
		Q.pop();
		for(int i = 0;i <= 25;i++) {
			if(ch[u].son[i]) {
				ch[ch[u].son[i]].fail = ch[ch[u].fail].son[i];
				Q.push(ch[u].son[i]);
			}
			else ch[u].son[i] = ch[ch[u].fail].son[i];
		}
	}
}
void iste() {
	int u = 1, m = strlen(s +1), sum = 0;
	for(int i = 1;i <= m;i++) {
		int c = ch[u].son[s[i] - 'a'];
		while(c && !vis[c]) {
			sum += p[c];
			vis[c] = 1;
			c = ch[c].fail;
		}
		u = ch[u].son[s[i] - 'a'];
	}
	cout <<sum <<endl;
}
int main() {
	scanf("%d", &n);
	for(int i = 1;i <= n;i++) {
		cin >> mp + 1;
		build();
	}
	fail_find();
	cin >> s + 1;
	iste();
} 

用加强版的样例

6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha

就可以卡掉, 应该输出5, 但是输出1