while(j>0 && s[i]!=s[j]){
            j = pi[j-1];
        }
        if(s[i]==s[j]){
            j++;
        pi[i] = j;
        }
    }
    return pi;
}
int strStr(string haystack, string needle) {
    vector<int> prefix = prefix_function(needle);
    int pos=-1;
    int j=0,i=0;
    while(i<haystack.size()){
        if(haystack[i]==needle[j]){
            i++;
            j++;
        }
        else{
            if(j!=0){
                j = prefix[j-1];
            }
            else i++;
        }
        if(j==needle.size()){
            pos = i-needle.size();
            break;
        }
    }
    return pos;
}