记录编号	424165	评测结果	AAAAAAAAAA
题目名称	[NOIP 2011]统计单词数	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2017-07-12 21:21:13	内存使用	1.52 MiB

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

#define MAXN (1000010)

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(char *s) { 
    char tmp = getc();
    while(!isalpha(tmp)) tmp = getc();
    int len = 0;
    while(isalpha(tmp))
        *(s++) = tolower(tmp), ++len, tmp = getc();
    *(s) = ' ';
    *(s + 1) = '\0';
    return len + 1;
}

inline int read_line(char *s) { 
    char tmp = getc();
    int len = 0;
    while(tmp == '\n' || tmp == '\r') tmp = getc();
    while(tmp ^ '\n' && tmp ^ '\r' && tmp ^ EOF) 
        *(s++) = tolower(tmp), ++len, tmp = getc();
    *(s) = ' ';
    *(s + 1) = '\0';
    return len + 1;
}

inline void get_next(void);
inline void kmp(void);

char s1[20], s2[MAXN];
int len1, len2, ans1, ans2;
int Next[20];

int main() { 
#ifndef LOCAL
    freopen("stat.in", "r", stdin);
    freopen("stat.out", "w", stdout);
#endif
    *s1 = *s2 = ' ';
    len1 = read(s1 + 1) + 1;
    len2 = read_line(s2 + 1) + 1;

    get_next();
    kmp();

    if(!ans2) printf("-1\n");
    else printf("%d %d\n", ans2, ans1);
    return 0;
}

inline void get_next(void) { 
    int k = (Next[0] = -1), j = 0;
    while(j < len1) { 
        if(k == -1 || s1[j] == s1[k]) { 
            ++j, ++k;
            Next[j] = k;
        } else k = Next[k];
    }
    return ;
}

inline void kmp(void) { 
    int i = 0, j = 0;
    while(i < len2) { 
        while(i < len2 && j < len1) { 
            if(j == -1 || s2[i] == s1[j]) ++i, ++j;
            else j = Next[j];
        }
        if(j == len1) { 
            if(!ans2) ans1 = i - j;
            ++ans2;
            j = Next[j];
        } else return;
    }
    return;
}