记录编号	324118	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]统计单词数	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.172 s
提交时间	2016-10-17 19:58:24	内存使用	0.34 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
class SAM
{
    int last, size;
public:
    struct state
    {
        int link;
        int len;
        int next[26];
        void init()
        {
            len = 0;
            link = -1;
            memset(next, 0, sizeof(next));
        }
    }st[233];
    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();
                memcpy(st[clone].next, st[q].next, sizeof(st[q].next));
                st[clone].len = st[p].len+1;
                st[clone].link = st[q].link;
                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;
    }
}sam;

int main()
{
    freopen("stat.in", "r", stdin);
    freopen("stat.out", "w", stdout);
    string a, b;
    getline(cin, a);
    getline(cin, b);
    for(int i = 0; i < a.length(); i++)
        sam.expand((a[i]&(~32))-'A');
    int cur = 0;
    int tmp = 0;
    int cnt = 0, pos = -1;
    int lastbk = -1;
    for(int i = 0; i < b.length(); i++)
    {
        if(b[i] == ' ')
        {
            lastbk = i;
            continue;
        }
        int c = (b[i]&(~32))-'A';
        if(sam.st[cur].next[c])
        {
            tmp++;
            cur = sam.st[cur].next[c];
        }else
        {
             while(~cur && !sam.st[cur].next[c])
                 cur = sam.st[cur].link;
             if(cur == -1)
                 cur = tmp = 0;
             else
             {
                 tmp = sam.st[cur].len+1;
                 cur = sam.st[cur].next[c];
             }
        }
        if(tmp == a.length())
        {
            if(lastbk == i-a.length() && (i+1 == b.length() || b[i+1] == ' '))
            {
                cnt++;
                if(pos == -1)
                    pos = i-a.length()+1;
            }
        }
    }
    if(cnt == 0)
        puts("-1");
    else
        printf("%d %d\n", cnt, pos);
    return 0;
}