一个玄学的问题
查看原帖
一个玄学的问题
90972
shitbro楼主2020/7/10 18:15
#include <iostream>
#include <cstdio>
#include <cstring>
#include<queue>
#define MAXN 500005

using namespace std;

int tr[MAXN][26],cnt[MAXN],ne[MAXN],tot = 0;
char s[MAXN * 2];
void insert(char *s) {
    int u = 0;
    for(int i = 0;i < strlen(s);i ++) {
        if(! tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++ tot;
        u = tr[u][s[i] - 'a'];
    }
    cnt[u] ++;
}
void build() {
    queue <int> q;
    for(int i = 0;i < 26;i ++) {
        if(tr[0][i]) q.push(tr[0][i]);
    }
    while(!q.empty()) {
        int t = q.front();
        q.pop();
        for(int i = 0;i < 26;i ++) {	
            int p = tr[t][i];
            if(! p) tr[t][i] = tr[ne[t]][i];
            else {
                ne[p] = tr[ne[t]][i];
                q.push(p);
            }
        }
    } 
}
int main() {
    int n; scanf("%d",&n);
    for(int i = 1;i <= n;i ++) {
        scanf("%s",s);
        insert(s);
    }
    build();
    int res = 0;
    scanf("%s",s);
    for(int i = 0,j = 0;i < strlen(s);i ++) {
        j = tr[j][s[i] - 'a'];
        int p = j;
        while(p && cnt[p] // 这个地方加上cnt[p]两个都会tle但如果不加反而第二个会对) {
            res += cnt[p];
            cnt[p] = 0;
            p = ne[p];
        }
    }
    printf("%d\n",res);
}
2020/7/10 18:15
加载中...