KMP

#include <iostream>
using namespace std;

void computeLps(int lps[],string s2){
    lps[0]=0;
    int m=s2.length();
    int len=0;
    int i=1;
    while(i<m){
        //if character matches
        if(s2[len]==s2[i]){
            len++;
            lps[i]=len;
            i++;
        }
        else{
            if(len!=0)
                len=lps[len-1];
            else{
                lps[i]=0;
                i++;
            }
        }
    }
}

//function for string matching
void kmp(string s1, string s2){
    int n=s1.length();
    int m=s2.length();

    int lps[m];
    computeLps(lps,s2);

    int i=0; //index for string
    int j=0; //index for matching string

    while(i<n){
        //if character of pattern matched with character of string
        if(s1[i]==s2[j]){
            i++;
            j++;
        }
        //pattern found in string
        if(j==m){
            cout<<"pattern found at index " << i-j<<endl;
            j=lps[j-1];
        }
        //if not matched
        else if(i<n && s1[i]!=s2[j]){
            //decrease lps till the last matched char
            if(j!=0)
                j=lps[j-1];
            else
                i++;
        }
    }
}


int main() {
    string s1, s2;
    cin>>s1>>s2;
    // cout<<s1<<" "<<s2;
    kmp(s1,s2);
    return 0;
}