2点WA了求调
查看原帖
2点WA了求调
749301
AmiyaCast楼主2023/5/27 15:45

2点WA了求调 检查不出错误呜呜 求求dalao帮帮

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 1e6 + 7;
struct Node{
	int to[26];
	int fail, end, vis;
}t[N];
int cnt = 0;
void build_Trie(char *s)
{
	int len = strlen(s + 1), p = 0;
	for(int i = 1; i <= len; ++i)
	{
		if(!t[p].to[s[i] - 'a'])
			t[p].to[s[i] - 'a'] = ++cnt;
		p = t[p].to[s[i] - 'a'];
	}
	t[p].end++;
}
int q[N], hd = 0, tl = 0;
void build_fail(){
	for(int i = 0; i <= 25; ++i)
	{
		int to = t[0].to[i];
		if(to) t[to].fail = 0;
		q[++tl] = to;
	}
	while(hd < tl)
	{
		int tmp = q[++hd];
		int tmp_fail = t[tmp].fail;
		for(int i = 0; i <= 25; ++i)
		{
			int to = t[tmp].to[i];
			if(to)
			{
				t[to].fail = t[tmp_fail].to[i];
				q[++tl] = to;
			}else{
				t[tmp].to[i] = t[tmp_fail].to[i];
			}
		}
	}
}
int sum(char *str)
{
	int ans = 0;
	int len = strlen(str + 1);
	int p = 0;
	for(int i = 1; i <= len; ++i)
	{
		p = t[p].to[str[i] - 'a'];
		for(int j = p; j && t[j].vis != -1; j = t[j].fail)
		{
			ans += t[j].end;
			t[j].vis = -1;
		}
	}
	return ans;
}

char s[N];
int main(){
	int n; scanf("%d", &n);
	for(int i = 1; i <= n; ++i){
		scanf("%s", s + 1);
		build_Trie(s);
	}
	scanf("%s", s + 1);
	printf("%d\n", sum(s));
	return 0;
}


2023/5/27 15:45
加载中...