记录编号	186569	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]统计单词数	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	0.154 s
提交时间	2015-09-13 16:10:46	内存使用	1.27 MiB

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
const int inf=1061109567;
const int maxn=1000010;
const int maxm=21;
const int mod=10007;

char a[maxn];
char b[maxm];
int alen,blen;
int next[maxm];
int cnt,pos;

void get_next()
{
    int i=0,j=-1;
    next[0]=-1;
    while(i<blen)
    {
        while(j!=-1&&b[i]!=b[j]) j=next[j];
        i++;j++;next[i]= (b[i]!=b[j]) ? j : next[j];
        //next[i]=j;
    }
}

void KMP()
{
    get_next();
    int i=0,j=0;
    cnt=0,pos=-1;
    while(i<alen)
    {
        while(j!=-1&&a[i]!=b[j]) j=next[j];
        i++;j++;
        if(j==blen)
        {
            if(pos==-1) pos=i-j;
            cnt++;
        }
    }
}

int main()
{
    freopen("stat.in","r",stdin);
    freopen("stat.out","w",stdout);
    //clock_t st=clock();
    int i=1;
    while(scanf("%c",&b[i])==1&&b[i]!='\n')
    {
        if(b[i]>='A'&&b[i]<='Z') b[i]=b[i]-'A'+'a';
        i++;
    }
    b[0]=b[i]=' ';blen=i+1;i=1;
    while(scanf("%c",&a[i])==1)
    {
        if(a[i]>='A'&&a[i]<='Z') a[i]=a[i]-'A'+'a';
        i++;
    }
    a[0]=a[i]=' ';alen=i+1;
    //printf("%d %d\n",alen,blen);
    KMP();
    if(cnt==0) printf("-1\n");
    else printf("%d %d\n",cnt,pos);
    //clock_t ed=clock();
    //printf("\nTime used : %.7lf Ms\n",double(ed-st)/CLOCKS_PER_SEC);
    return 0;
}