hdu2896

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
const int cha = 128;
const int maxa = 110000;
int n, m, k;
struct Tire{
    int next[maxa][cha], fail[maxa], end[maxa];
    int root, L;
    int newnode(){
        for(int i = 0; i < cha; i++){
            next[L][i] = -1;
        }
        end[L++] = 0;
        return L-1;
    }
    void init(){
        L = 0;
        root = newnode();
    }
    void insert(char buf[], int k){
        int len = strlen(buf);
        int now = root;
        for(int i = 0; i < len; i++){
            if(next[now][buf[i]] == -1)
                next[now][buf[i]] = newnode();
            now = next[now][buf[i]];
            //printf("%d ", now);
        }//puts("");
        end[now] = k;
    }
    void build(){
        queue<int>Q;
        fail[root] = root;
        for(int i = 0; i < cha; i++){
            if(next[root][i] == -1)
                next[root][i] = root;
            else{
                fail[next[root][i]] = root;
                Q.push(next[root][i]);
            }
        }
        while(!Q.empty()){
            int now = Q.front();
            Q.pop();
            for(int i = 0; i < cha; 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 ans[505];
    int solve(char *s, int id){
        int now = 0;
        int flag = 0;
        memset(ans, 0, sizeof(ans));
        for(int i = 0; s[i]; i++){
            now = next[now][s[i]];
            int j = now;
            while(j){
                if(end[j]){//printf("*%d ", end[j]);
                    ans[end[j]] = true;
                    flag = 1;
                }
                j = fail[j];
            }
        }
        if(!flag) return 0;
        printf("web %d:",id);
        for(int i = 1;i <= n;i++)
            if(ans[i])
                printf(" %d",i);
        printf("\n");
        return 1;

    }
};
char buf[10015];
Tire ac;
int main(){
    scanf("%d", &n);
    ac.init();
    for(int i = 1; i <= n; i++){
        scanf("%s", buf);
        ac.insert(buf, i);
    }
    ac.build();
    scanf("%d", &m);
    int sum = 0;
    for(int i = 1; i <= m; i++){
        scanf("%s", buf);
        if(ac.solve(buf,i))
            sum ++;
    }
        printf("total: %d\n",sum);
}
/*
abcdefg
bcdefg
cdef
de
e
ssaabcdefg


*/