KMP algo

#include <bits/stdc++.h>

using namespace std;


void findPattern(vector<int> &prefix,string txt){
    int idx=0,i=1;
    while(i<txt.length()){
        if(txt[i]==txt[idx]){
            prefix[i++]= ++idx;
        }
        else{
            if(idx==0)i++;
            else idx=prefix[idx-1];
        }
    }
}

void find(string str, string txt){
    int m=str.length(),n=txt.length();

    vector<int>prefix(n);
    findPattern(prefix,txt);
    int id=0,i=0;
    while(i<m){
        if(txt[id]==str[i])id++,i++;
        else{
            if(id==0)i++;
            else id=prefix[id-1];
        }

        if(id==n){
            cout<<i-id<<" ";
            id=prefix[id-1];
        }
    }
}
int main()
{
   string str="batmanandrobinarebat";
   string txt="bat";
   find(str,txt);
   return 0;
}