vector<int> prefix(string s){
vector<int> prefix(s.length(),0);
int j=0;
for(int i=1;i<s.length();i++)
{
if( s[i] == s[j] )
{
prefix[i]=j+1;
j++;
}
else{
while(s[j] != s[i]&&j!=0)
{
j = prefix[j-1];
}
if(s[j] == s[i]){
prefix[i] = prefix[j]+1;
j++;
}
}
}
return prefix;
}
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.length()==0)
return 0;
vector <int> vec=prefix(needle);
/* for(vector<int>:: iterator it = vec.begin(); it!=vec.end(); it++ )
{
cout<<*it<<endl;
}*/
int j=0,i=0;
for( i=0; i<haystack.length();)
{
if(haystack[i]==needle[j])
{
i++; j++;
}
else{while(haystack[i]!=needle[j] && j!=0)
{
j=vec[j-1];
}
if(haystack[i]==needle[j])
continue;
else i++;}
// cout<<i<<" "<<j<<endl;
if(j==needle.length()) return i-j;
}
return -1;
}
};