#include <stdio.h> #include <stdlib.h> #include<map> #include<algorithm> #include<iostream> #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=100010; int nex[maxn]; void getnex(char *p) { int len=strlen(p); int i=0,j=-1; nex[0]=-1; while(i<len){ while(j!=-1&&p[i]!=p[j]){ j=nex[j]; } nex[++i]=++j; } } void KMP(char *s,char *p) { getnex(p); int len1=strlen(s); int len2=strlen(p); int i=0,j=0; while(i<len1){ while(j!=-1&&s[i]!=p[j]){ j=nex[j]; } ++i; ++j; if(j==len2){ cout<<i-len2+1<<endl; return ; } } cout<<-1<<endl; } int main() { // char s1[100],s2[100]; // while(cin>>s1>>s2)KMP(s1,s2); return 0; } #include <stdio.h> #include <stdlib.h> #include<map> #include<algorithm> #include<iostream> #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=100010; int nex[maxn]; void getnex(char *p) { int len=strlen(p); int i=0,j=-1; nex[0]=-1; while(i<len){ while(j!=-1&&p[i]!=p[j]){ j=nex[j]; } nex[++i]=++j; } } void KMP(char *s,char *p) { getnex(p); int len1=strlen(s); int len2=strlen(p); int i=0,j=0; while(i<len1){ while(j!=-1&&s[i]!=p[j]){ j=nex[j]; } ++i; ++j; if(j==len2){ cout<<i-len2+1<<endl; return ; } } cout<<-1<<endl; } int main() { char s1[100],s2[100]; while(cin>>s1>>s2)KMP(s1,s2); return 0; }