50PTS求调
查看原帖
50PTS求调
565378
Orange1015楼主2023/5/26 11:55

rt.

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
int N,rt=0;
int ch[maxn][26],tot=0;
int flag[maxn];
int fail[maxn]; 
char s[maxn],t[maxn];
int ys(char c){
	return c-'a';
}
void insert(char s[]){
	int len=strlen(s),nw=rt;
	for(int i=0;i<len;i++){
		if(!ch[nw][ys(s[i])]){
			ch[nw][ys(s[i])]=++tot;
		}
		nw=ch[nw][ys(s[i])];
	}
	flag[nw]++;
}
void getFail(){
	queue<int> q;
	for(int i=0;i<26;i++){
		if(ch[rt][i]){
			fail[ch[rt][i]]=rt;
			q.push(ch[rt][i]);
		}
	}
	while(!q.empty()){
		int p=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(ch[p][i]){
				fail[ch[p][i]]=ch[fail[p]][i];
				q.push(ch[p][i]);
			}
			else{
				ch[p][i]=ch[fail[p]][i];
			}
		}
	}
}
int kmp(char t[]){
	int n=strlen(t);
	int cnt=0,p=rt;
	for(int i=0;i<n;i++){
		p=ch[p][s[i]-'a'];
		int k=p;
		for(int j=p;p&&flag[j]!=-1;j=fail[j]){
			cnt+=flag[j];
			flag[j]=-1;
		}
	}
	return cnt;
}
int main(){
	cin >> N;
	for(int i=1;i<=N;i++){
		cin >> s;
		insert(s);
	}
	getFail();
	cin >> t;
	cout << kmp(t);
	return 0;
}
2023/5/26 11:55
加载中...