Keywords Search

「爱情、让人受尽委屈。」 2022-08-07 05:37 115阅读 0赞

#include <stdio.h>
    #include <queue>
    #include <string.h>
    
    using namespace std;
    #define M 500010
    struct trie
    {
        int next[M][26], fail[M], end[M];
        int root, l;
    
        int newnode()
        {
            for(int i=0; i<26; i++) next[l][i] = -1;
            end[l++] = 0;
            return l-1;
        }
        void init()
        {
            l = 0;
            root = newnode();
        }
        void insert(char buf[])
        {
            int len = strlen(buf);
            int now = root;
            for(int i=0; i<len; i++){
                if(next[now][buf[i]-'a'] == -1) 
                    next[now][buf[i]-'a'] = newnode();
                now = next[now][buf[i]-'a'];
            }
            end[now]++;
        }
        void build()
        {
            queue<int>Q;
            fail[root] = root;
            for(int i=0; i<26; i++) {
                if(next[root][i] == -1)
                    next[root][i] = root;
                else{
                    fail[ next[root][i] ] = root;
                    Q.push( next[root][i] );
                }
            }
            while( Q.empty()!=true){
                int now = Q.front();
                Q.pop();
                for(int i=0; i<26; i++){
                    if(next[now][i] == -1){
                        next[now][i] = next[fail[now]][i];
                    }
                    else {
                        fail[ next[now][i] ] = next[ fail[now] ][i];
                        Q.push( next[now][i] );
                    }
                }
            }
        }
        int query(char buf[])
        {
            int len = strlen(buf);
            int now = root;
            int res = 0;
            for(int i=0; i<len; i++){
                now = next[now][buf[i]-'a'];
                int temp = now;
                while(temp != root){
                    res += end[temp];
                    end[temp] = 0;
                    temp = fail[temp];
                }
            }
            return res;
        }
    };
    char buf[1000010];
    trie ac;
    int main()
    {
        int t, n;
        scanf("%d", &t);
        while(t--){
            scanf("%d", &n);
            ac.init();
            for(int i=0; i<n; i++){
                scanf("%s", buf);
                ac.insert(buf);
            }
            ac.build();
            scanf("%s", buf);
            printf("%d\n", ac.query(buf));
        }
    
        return 0;
    }