RE求调
查看原帖
RE求调
757040
MuLinnnnn楼主2023/11/19 19:40
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
typedef long long ll;
#define endl '\n'
using namespace std;
const ll N = 1e6 + 3;
ll trie[N][26];
ll word[N];
ll fail[N];
ll cnt = 0;

inline void Insert(string s){
	ll o = 0; // root
	for(ll i = 0; i < s.length(); ++i){
		ll nxt = s[i] - 'a';
		if(!trie[o][nxt]){
			trie[o][nxt] = ++cnt;
		}
		o = trie[o][nxt];
	}
	word[o]++;
}

inline void getFail(){
	queue< ll > Q;
	for(ll i = 0; i < 26; ++i){
		if(trie[0][i]){
			fail[trie[0][i]] = 0;
			Q.push(trie[0][i]);
		}
	}
	while(!Q.empty()){
		ll now = Q.front();
		Q.pop();
		for(ll i = 0; i < 26; ++i){
			if(trie[now][i]){
				fail[trie[now][i]] = trie[fail[now]][i];
				Q.push(trie[now][i]);
			}else{
				trie[now][i] = trie[fail[now]][i];
			}
		}
	}
}

inline ll AC_Query(string s){
	ll ret = 0;
	for(ll i = 0; i < s.length(); ++i){
		ll now = trie[now][s[i]-'a'];
		for(ll j = now; j && word[j] != -1; j = fail[j]){
			ret += word[j];
			word[j] = -1;
		}
	}
	return ret;
}

int main(){
	ll n;
    cin >> n;
    for(ll i = 1; i <= n; ++i){
    	string s;
    	cin >> s;
    	Insert(s);
	}
	fail[0] = 0;
	getFail();
	string Find;
	cin >> Find;
	cout << AC_Query(Find) << endl;
	return 0;
}

rt!

2023/11/19 19:40
加载中...