学步园

题目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4114

题目的意思：

给你一个加密的字符串，让你用二进制表示，每六位一个字符

然后再用8位二进制表示一个明文的字符，这是翻译的过程。

给你一些病毒的暗文，再给你一些长的字符串的暗文

问你每个长字符串暗文中出现了几种病毒，看清楚，是几种，不是几个。我为此WA了一个下午

此题分两步，一是要翻译

而是裸的AC自动机

裸的AC是很简单的

但是翻译的坑很大。

暗文都是可见字符，但是翻译过来的是ASCII在0~255之间的

所以不能用char来保存翻译后的，得用int

相应的长度也要做变化。

完成翻译之后就是裸的AC自动机了。

在进行统计的时候要注意，如果这个字符串之前统计了，就不要统计了

因为是问的种数，我WA了一个下午啊，说多了都是眼泪啊。

下面上代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;

const int maxlb=80000;
int erjin[maxlb];
char p[10000];
char text[10000];
int changetmp[10000];

int cha(char c)
{
    if(c>='A'&&c<='Z')
        return c-'A';
    if(c>='a'&&c<='z')
        return c-'a'+26;
    if(c>='0'&&c<='9')
        return c-'0'+52;
    if(c=='+')
        return 62;
    return 63;
}



//先写转换函数
void change(char *s)
{
    int len=strlen(s);
    while(s[len-1]=='=')//忽略后面加入的=
        len--;
    s[len]='\0';
    memset(erjin,0,sizeof(erjin));
    for(int i=0;i<len;i++)
    {
        int tmp=cha(s[i]);
        for(int j=6*(i+1)-1;j>=6*i;j--)//把转换后的先换成二进制，每个字符六位
        {
            if(tmp&1)
                erjin[j]=1;
            tmp=tmp>>1;
        }
    }

    int len2 = len*6 / 8;
    for(int i=0;i<len2;i++)
    {
        int tmp=0;
        for(int j=8*i;j<=8*(i+1)-1;j++)
            tmp=(tmp<<1)+erjin[j];
        changetmp[i]=tmp;
    }
    changetmp[len2]=-1;
}

int findlen(int *s)
{
    int len = 0;
    while(s[len]>=0)
        len++;
    return len;
}

const int maxnode = 50000;
const int size_char=300;
int ans;

struct AC
{
    int ch[maxnode][size_char];
    int f[maxnode];
    int last[maxnode];
    int val[maxnode];
    bool vis[maxnode];
    int sz;

    void init()
    {
        sz=1;
        memset(ch[0],0,sizeof(ch[0]));
        memset(vis,false,sizeof(vis));
    }

    void tongji(int x)
    {
        if(x&&!vis[x])
        {
            ans++;
            vis[x]++;
            tongji(last[x]);
        }
    }

    void insert(int *s,int v)
    {
        int n=findlen(s);
        int u=0;
        for(int i=0;i<n;i++)
        {
            int c=s[i];
            if(!ch[u][c])
            {
                memset(ch[sz],0,sizeof(ch[sz]));
                val[sz]=0;
                ch[u][c]=sz++;
            }
            u=ch[u][c];
        }
        val[u]=v;
    }

    void find(int *T)
    {
        int n=findlen(T);
        int u=0;
        for(int i=0;i<n;i++)
        {
            int c=T[i];
            while(u&&!ch[u][c])//沿着失配边走
                u=f[u];
            u=ch[u][c];
            if(val[u])
                tongji(u);
            else if(last[u])
                tongji(last[u]);
        }
    }

    //构造f和last
    void getfail()
    {
        queue<int>q;
        int u=0;
        f[0]=0;
        for(int i=0;i<size_char;i++)
        {
            u=ch[0][i];
            if(u)
            {
                f[u]=0;
                q.push(u);
                last[u]=0;
            }
        }

        while(!q.empty())
        {
            int r=q.front();
            q.pop();
            for(int i=0;i<size_char;i++)
            {
                u=ch[r][i];
                if(!u)
                    continue;
                q.push(u);
                int v=f[r];
                while(v&&!ch[v][i])
                    v=f[v];
                f[u]=ch[v][i];
                last[u] = val[f[u]] ? f[u] : last[f[u]];
            }
        }
    }

};


AC ac;

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        ac.init();
        for(int i=1;i<=n;i++)
        {
            scanf("%s",p);
            change(p);
            ac.insert(changetmp,i);
        }
        ac.getfail();
        int m;
        scanf("%d",&m);
        while(m--)
        {
            ans=0;
            memset(ac.vis,false,sizeof(ac.vis));
            scanf("%s",text);
            change(text);
            ac.find(changetmp);
            printf("%d\n",ans);
        }
        printf("\n");
    }
    return 0;
}