WA #2 求助%%
查看原帖
WA #2 求助%%
719201
INT_1024楼主2024/8/23 20:48

码风可能有点乱

#include<iostream>
#include<queue>
using namespace std;
#define int long long
int test_num,point_value=1;
string check;
struct Ac_automaton{
	int fail_cur;
	int cnt_Size;
	int find_value;
}Ac_tree[1000005];
int trie[1000005][30];
bool flag[1000005];
void Ac_insert(string into){
	int cur=1;
	for(int i=0;i<into.size();i++){
		if(!trie[cur][into[i]-'a'])
			trie[cur][into[i]-'a']=++point_value;
		cur=trie[cur][into[i]-'a'];
	}
	Ac_tree[cur].find_value++;
	Ac_tree[cur].cnt_Size=into.size();
}
void Make_fail(){
	queue<int> make;
	make.push(1);
	while(!make.empty()){
		for(int i=0;i<26;i++){
			if(trie[make.front()][i]){
				int last_fail=Ac_tree[make.front()].fail_cur;
				if(trie[last_fail][i]!=0)
					Ac_tree[trie[make.front()][i]].fail_cur=trie[last_fail][i];
				else Ac_tree[trie[make.front()][i]].fail_cur=1;
				make.push(trie[make.front()][i]);
			}
		}
		make.pop();
	}
}
int Ac_search(string find_str){
	int search_num=0,cur=1;
	for(int i=0;i<find_str.size();i++){
		while(!trie[cur][find_str[i]-'a'] && Ac_tree[cur].fail_cur) cur=Ac_tree[cur].fail_cur;
		if(trie[cur][find_str[i]-'a']) cur=trie[cur][find_str[i]-'a'];
		else continue;
		int cnt_cur=cur;
		while(Ac_tree[cnt_cur].fail_cur && !flag[cnt_cur]){
			flag[cnt_cur]=true;
			search_num+=Ac_tree[cnt_cur].find_value;
			Ac_tree[cnt_cur].find_value=0;
			cnt_cur=Ac_tree[cnt_cur].fail_cur;
		}
	}
	return search_num;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>test_num;
	for(int i=1;i<=test_num;i++){
		string temp;cin>>temp;
		Ac_insert(temp);
	}
	Make_fail();
	cin>>check;
	cout<<Ac_search(check);
	return 0;
}
2024/8/23 20:48
加载中...