病毒侵袭

佚名 6年前 (2019-04-10) 随笔 685人围观抢沙发百度已收录

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#include <sstream>
#include <iostream>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
using namespace std;
#define ll long long
#define re register
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define P pair<int,int>
const int N=1e6+10;
const int mod=1e9+7;
void read(int &a)
{
    a=0;
    int d=1;
    char ch;
    while(ch=getchar(),ch>'9'||ch<'0')
        if(ch=='-')
            d=-1;
    a=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')
        a=a*10+ch-'0';
    a*=d;
}
void write(int x)
{
    if(x<0)
        putchar(45),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
struct note
{
    int next;
    int to[100];
    int bz;
}trie[N];
int tot;
char s[10001];
bool f[505];
bool flag;
inline void ins(int k)
{
    int len=strlen(s);
    int now=0;
    for(re int i=0;i<len;i++)
    {
        int x=s[i]-31;
        if(!trie[now].to[x])
            trie[now].to[x]=++tot;
        now=trie[now].to[x];
    }
    trie[now].bz=k;
}
inline void built()
{
    queue <int> q;
    for(re int i=1;i<=95;i++)
        if(trie[0].to[i])
            trie[trie[0].to[i]].next=0,q.push(trie[0].to[i]);
    while(!q.empty())
    {
        int p=q.front();
        q.pop();
        for(re int i=1;i<=95;i++)
        {
            if(trie[p].to[i])
                trie[trie[p].to[i]].next=trie[trie[p].next].to[i],q.push(trie[p].to[i]);
            else
                trie[p].to[i]=trie[trie[p].next].to[i];
        }
    }
}
inline void solve()
{
    int len=strlen(s);
    int now=0;
    for(re int i=0;i<len;i++)
    {
        int x=s[i]-31;
        now=trie[now].to[x];
        for(re int j=now;j&&!f[trie[j].bz];j=trie[j].next)
        {
            if(trie[j].bz)
                f[trie[j].bz]=1,flag=1;
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    read(n);
    for(re int i=1;i<=n;i++)
    {
        scanf("%s",s);
        ins(i);
    }
    built();
    int m;
    read(m);
    int sum=0;
    for(re int i=1;i<=m;i++)
    {
        flag=0;
        memset(f,0,sizeof(f));
        scanf("%s",s);
        solve();
        if(flag)
        {
            sum++;
            printf("web %d:",i);
            for(re int j=1;j<=n;j++)
                if(f[j])
                    putchar(' '),write(j);
            putchar('\n');
        }
    }
    printf("total: %d\n",sum);
    return 0;
}