记录编号	324522	评测结果	AAAAAT
题目名称	AC自动机	最终得分	83
用户昵称	sxysxy	是否通过	未通过
代码语言	C++	运行时间	1.249 s
提交时间	2016-10-18 11:44:03	内存使用	68.97 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <list>
#include <cctype>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
using namespace std;
#define MAXN 1000001
int fast_read()
{
    int r;
    char c;
    bool sig = false;
    while(c = getchar())    
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }else if(c == '-')sig = true;
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return sig? -r:r;
}

class SAM
{
    int last, size;
public:
    struct state
    {
        int link;
        int len;
        map<int, int> next;
        void init()
        {
            len = 0;
            link = -1;
        }
    }st[MAXN<<1];
    int rec[MAXN<<1];
    SAM()
    {
        last = size = 0;
        newst();
    }
    int newst()
    {
        st[size++].init();
        return size-1;
    }
    void expand(int c)
    {
        int cur = newst();
        st[cur].len = st[last].len+1;
        int p;
        for(p = last; ~p && !st[p].next[c]; p = st[p].link)
            st[p].next[c] = cur;
        if(p == -1)
            st[cur].link = 0;
        else
        {
            int q = st[p].next[c];
            if(st[q].len == st[p].len+1)
                st[cur].link = q;
            else
            {
                int clone = newst();
                st[clone].next = st[q].next;
                st[clone].len = st[p].len+1;
                st[clone].link = st[q].link;
                rec[clone] = rec[q];
                for(; ~p && st[p].next[c] == q; p = st[p].link)
                    st[p].next[c] = clone;
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
        while(cur != -1)
        {
            rec[cur]++;
            cur = st[cur].link;
        }
    }
    int count(const char *s, int len)
    {
        int c = 0;
        for(int i = 0; i < len; i++)
            if(!(c = st[c].next[s[i]-'a']))return 0;
        return rec[c];
    }
}sam;

string ss[233];
int main()
{
    freopen("ACautomata.in", "r", stdin);
    freopen("ACautomata.out", "w", stdout);
    int m;
    cin >> m;
    for(int i = 1; i <= m; i++)cin>>ss[i];
    string s;
    cin >> s;
    for(int i = 0; i < s.length(); i++)
        sam.expand(s[i]-'a');
    
    for(int i = 1; i <= m; i++)
    {
        string &t = ss[i];
        cout << t << ' ' << sam.count(t.c_str(), t.length()) << '\n';
    }
    return 0;
}