#include #include #include int next[1000]; int nextval[1000]; void get_next(char *str) { int i = 1 , j = 0, len; str[0] = strlen( (str + 1)); next[1] = 0; while ( i < str[0] ) { if ( j == 0 || str[i] == str[j] ) i++, j++, next[i] = j; else j = next[j]; } } void get_nextval ( char *str) { int i = 1, j = 0; nextval[1] = 0; str[0] = strlen (str + 1); while ( i < str[0] ) { if (str[i] == str[j] || j == 0) { i++, j++; if (str[i] != str[j] ) nextval[i] = j; else nextval[i] = nextval[j]; } else j = nextval[j]; } } int index_kmp ( char *S, char *T) { int i = 1, j = 1; S[0] = strlen(S + 1); T[0] = strlen(T + 1); while ( i <= S[0] && j <= T[0]) { if ( j == 0 || T[j] == S[i] ) { i++, j++; } else j = nextval[j]; } if ( j > T[0]) return i - T[0]; return 0; } int main( ) { char ch[30]; char sh[100]; while (scanf("%s%s",sh+1, ch+1) != EOF ) { memset(next, 0, sizeof(next)); get_next(ch); get_nextval(ch); printf("%d\n",index_kmp(sh,ch)); } return 0; }