//串的模式匹配算法
//KMP算法，时间复杂度为O(n+m)
#include <iostream>
#include <string>
#include <cstring>
using namespace std; //-----串的定长顺序存储结构-----
#define MAXLEN 255 //串的最大长度
typedef struct {
char ch[MAXLEN + ]; //存储串的一维数组
int length; //串的当前长度
}SString; int Next[MAXLEN + ];
int nextval[MAXLEN + ]; int Index_KMP1(SString S, SString T, int pos)
{//利用模式串T的Next函数求T在主串S中的第pos个字符之后的位置
//其中，T非空，1<=pos<=S.length
int i = pos, j = ;
while (i <= S.length && j <= T.length) //两个串均未比较到串尾
{
if (j == || S.ch[i] == T.ch[j]) { ++i; ++j; } //继续比较后继字符
else j = Next[j]; //模式串向右移动
}
if (j > T.length) return i - T.length; //匹配成功
else return ; //匹配失败
} int Index_KMP2(SString S, SString T, int pos)
{
int i = pos, j = ;
while (i <= S.length && j <= T.length)
{
if (j == || S.ch[i] == T.ch[j]) { ++i; ++j; }
else j = nextval[j];
}
if (j > T.length) return i - T.length;
else return ;
} void get_next(SString T, int Next[])
{//求模式串T的Next函数值并存入数组Next
int i = , j = ;
Next[] = ;
while (i < T.length)
{
if (j == || T.ch[i] == T.ch[j]) { ++i; ++j; Next[i] = j; }
else j = Next[j];
}
} void get_nextval(SString T, int nextval[])
{//求模式串T的Next函数修正值并存入数组nextval
int i = , j = ;
nextval[] = ;
while (i < T.length)
{
if (j == || T.ch[i] == T.ch[j])
{
++i; ++j;
if (T.ch[i] != T.ch[j]) nextval[i] = j;
else nextval[i] = nextval[j];
}
else j = nextval[j];
}
} int main()
{
SString A, B;
A.ch[] = B.ch[] = ' ';
while (scanf("%s%s", A.ch + , B.ch + ) == )
{
A.length = strlen(A.ch + );
B.length = strlen(B.ch + );
get_next(B, Next);
get_nextval(B, nextval);
//修正之后匹配更快，结果相同
int ans1 = Index_KMP1(A, B, ), ans2 = Index_KMP2(A, B, );
printf("%d\t%d\n", ans1, ans2);
}
return ;
}