样例2 3没过,却AC了,求调
查看原帖
样例2 3没过,却AC了,求调
578029
ivyjiao楼主2024/6/18 19:28
#include<bits/stdc++.h>
using namespace std;
int n,trie[1000001][27],fail[1000001],cnt,vis[1000001];
string s[1000001],t;
int getnum(char x){
    return (int)(x-'a');
}
void insert(string s){
    int u=0;
    for(int i=0;i<s.size();i++){
        int c=getnum(s[i]);
        if(!trie[u][c]) trie[u][c]=++cnt;
        u=trie[u][c];
    }
	vis[u]++;
}
void getfail(){
    queue<int>q;
    for(int i=0;i<26;i++){
        if(trie[0][i]) q.push(trie[0][i]);
    }
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            if(trie[u][i]){
				fail[trie[u][i]]=trie[fail[u]][i];
				q.push(trie[u][i]);
			}
            else trie[u][i]=trie[fail[u]][i];
        }
    }
}
int query(string t){
    int u=0,cnt=0;
    for(int i=1;t[i];i++){
        u=trie[u][t[i]-'a'];
        for(int j=u;j&&vis[j]!=-1;j=fail[j]){
            cnt+=vis[j];
            vis[j]=-1;
        }
    }
    return cnt;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        insert(s[i]);
    }
    getfail();
    cin>>t;
    cout<<query(t);
}
2024/6/18 19:28
加载中...