#2WA
查看原帖
#2WA
303132
Okimoto楼主2020/12/14 19:18
#include <stdio.h>
#include <vector>
#include <string.h>
#include <queue>
#include <set>
using namespace std;
struct node{
    char vl;
    int ch[26];
    int sp;
    int dp;
    int fl;
    int as;
    node(){
        sp = 0;
        dp = 0;
        fl = 0;
        as = 0;
    }
};
int n, pool = 1;
char s[2000007];
node t[2000007];
bool b[2000007];
int main(){
    //freopen("in.in", "r", stdin);
    scanf("%d", &n);
    for(int i = 0; i < n; i ++){
        scanf("%s", s);
        int k = 1;
        int len = strlen(s);
        for(int j = 0; j < len; j ++){
            char c = s[j];
            if(t[k].ch[c - 'a'] == 0){
                t[k].ch[c - 'a'] = ++ pool;
                t[pool].sp = k;
                t[pool].vl = c;
                t[pool].dp = j + 1;
            }
            k = t[k].ch[c - 'a'];
        }
        t[k].as += 1;
    }
    queue <int> q;
    q.push(1);
    while(!q.empty()){
        int k = q.front();
        q.pop();
        if(t[k].dp > 1){
            t[k].fl = 1;
            char c = t[k].vl;
            int u = t[k].sp;
            for(; u != 1; u = t[u].sp){
                int v = t[u].fl;
                if(t[v].ch[c - 'a']){
                    t[k].fl = t[v].ch[c - 'a'];
                    break;
                }
            }
        }
        else if(t[k].dp == 1){
            t[k].fl = 1;
        }
        for(int i = 0; i < 26; i ++){
            if(t[k].ch[i]){
                q.push(t[k].ch[i]);
            }
        }
    }
    scanf("%s", s);
    int k = 1;
    int ans = 0;
    t[1].fl = 0;
    int len = strlen(s);
    for(int i = 0; i < len && k != 0;){
        char c = s[i];
        if(t[k].ch[c - 'a']){
            k = t[k].ch[c - 'a'];
            for(int u = k; u != 1 && !b[u]; u = t[u].fl){
                ans += t[u].as;
                t[u].as = 0;
                b[u] = true;
            }
            i ++;
        }
        else{
            if(k == 1){
                i ++;
            }
            else{
                k = t[k].fl;
            }
        }
    }
    printf("%d", ans);
    return 0;
}

2020/12/14 19:18
加载中...