病毒侵袭

谁借莪１个温暖的怀抱￠ 2022-08-07 05:37 212阅读 0赞

#include <cstdio>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    int total;
    char ch[10010];
    struct trie
    {
        int next[500*201][128], fail[500*201], end[500*201], root, l;
        int newnode()
        {
            for(int i=0; i<128; i++)    next[l][i] = -1;
            end[l++] = 0;
            return l-1;
        }
        void init()
        {
            l = 0;
            root = newnode();
            total = 0;
        }
        void insert(char ch[], int id)
        {
            int len = strlen(ch);
            int now=root;
            for(int i=0; i<len; i++){
                if(next[now][(int)ch[i]]==-1)
                    next[now][(int)ch[i]] = newnode();
                now = next[now][(int)ch[i]];
            }
            end[now]=id;
        }
        void build()
        {
            queue<int>Q;
            int now;
            fail[root] = root;
            for(int i=0; i<128; i++){
                if(next[root][i] == -1)
                    next[root][i] = root;
                else{
                    fail[ next[root][i] ] = root;
                    Q.push( next[root][i] );
                }
            }
            while( !Q.empty() ) {
                now = Q.front();    Q.pop();
                for(int i=0; i<128; 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]);
                    }
                }
            }
        }
        void query(char ch[], int num)
        {
            bool id[510], flag=false;
            int len = strlen(ch);
            int now=root;
            memset(id, false, sizeof(id));
            for(int i=0; i<len; i++)  {
                    //printf("kkk:%c %d\n", ch[i], now);
                now = next[now][ (int)ch[i] ];
    
                int temp=now;
                while(temp != root){
                    if(end[temp] != 0){
                        id[end[temp]] = true;
                        flag = true;
                    }
                    temp = fail[temp];
                }
            }
            if(flag) {
                total++;
                printf("web %d:", num);
                for(int i=0; i<505; i++){
                    if( id[i] )
                        printf(" %d", i);
                }
                printf("\n");
            }
        }
        void debug()
        {
            int now = root;
            for(int i=0; i<128; i++){
                while( next[now][i]!=root )
                {
                    printf("%c %d", i, end[next[now][i]]);
                    now = next[now][i];
                }
                now = root;
    
            }printf("\n");
        }
    };
    trie ac;
    int main()
    {
        int n, m;
    
        while(scanf("%d", &n) != -1){
            ac.init();
            for(int i=1; i<=n; i++){
                scanf("%s", ch);
                ac.insert(ch, i);
            }
            ac.build();
            //ac.debug();
            scanf("%d", &m);
            for(int i=1; i<=m; i++){
                scanf("%s", ch);
                ac.query(ch, i);
            }
            printf("total: %d\n", total);
        }
        return 0;
    }