#include <iostream>
#include <string.h>
using namespace std;
void get_next(string T,int *next)
{
int i=1;
int j=0;
next[1]=0;
int len = T.length();
while (i<len) {
if (0 == j||T[i] == T[j]) {
i++;
j++;
if (T[i] != T[j]) {
next[i] = j;
}
else{
next[i]=next[j];
}
}
else
{
j = next[j];
}
}
}
int index_KMP(string S,string T,int pos)
{
int i=pos;
int j =1;
int next[255];
get_next(T, next);
int len1 = S.length();
int len2 =T.length();
while (i<=len1 && j<=len2) {
if (0 == S[i] == T[j]) {
i++;
j++;
}
else
{
j = next[j];
}
}
if (j > len1) {
return i-len1;
}else
{
return 0;
}
}
int main(int argc, const char * argv[]) {
string S ="1123455";
string T ="11";
cout<<index_KMP(S, T, 0);
return 0;
}