n = 1的点T了,n<=1e6过了,求调
查看原帖
n = 1的点T了,n<=1e6过了,求调
857730
nnnbbblqy楼主2024/7/18 19:05
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int ch[N][30] , fail[N] , cnt[N] , mp[N];
int tot , n , m , sum , ans;
void ins(string c , int len){
	int now = 0;
	for(int i = 1; i <= len; i ++){
		if(!ch[now][c[i] - 'a'])
		    ch[now][c[i] - 'a'] = ++ tot;
		now = ch[now][c[i] - 'a'];
	}
	mp[++ sum] = now;
} 
void build_fail(){
	queue<int> q;
	for(int i = 0; i < 26; i ++) if(ch[0][i]) q.push(ch[0][i]);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int i = 0; i < 26; i ++){
			if(ch[u][i]) fail[ch[u][i]] = ch[fail[u]][i] , q.push(ch[u][i]);
			else ch[u][i] = ch[fail[u]][i];
		}
	}
} 
void query(string c , int len){
	int now = 0;
	for(int i = 1; i <= len; i ++){
		now = ch[now][c[i] - 'a'];
		for(int j = now; j ; j = fail[j])
		    ++ cnt[j];
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++){
    	string a;
    	cin >> a;
    	int len = a.size();
    	a = ' ' + a;
    	ins(a , len);
	}
	build_fail();
	string b;
	cin >> b;
	int len = b.size();
	b = ' ' + b;
	query(b , len); 
	for(int i = 1; i <= n; i ++) ans += (cnt[mp[i]] >= 1);
	cout << ans;
    return 0;
}
2024/7/18 19:05
加载中...