kmp

///:-)
#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define inf 2000000000
#define sc(n) scanf("%d", &n)
#define Aktaruzzaman using
#define scl(n) scanf("%lld", &n)
#define scd(n) scanf("%lf", &n)
#define pi (2.0*acos(0.0))
#define Pramanik namespace std;
#define vsort(v)   sort(v.begin(),v.end())
#define ull unsigned long long int
#define mem(a, b) memset(a, b, sizeof a)
#define cf 100009
Aktaruzzaman Pramanik

string txt, pat;
int lps[cf];

void buildLps()
{
    int M = pat.size();
    lps[0]=0;
    int j=0;
    int i=1;
    while(i<M)
    {
        if(pat[j]==pat[i]){
            lps[i]=++j;
            i++;
        }
        else{
            if(j!=0)
            {
                j = lps[j-1];
            }
            else{
                lps[i]=0;
                i++;
            }
        }
    }

}

void kmp()
{
    buildLps();

    int M = pat.size();
    int N = txt.size();
    int i=0;
    int j=0;
    while(i<N)
    {
        if(txt[i]==pat[j])
        {
            i++;
            j++;
        }

        if(j==M)
        {
            printf("Found at position : %d\n", i-j);
            j = lps[j-1];
        }
        else if(txt[i]!=pat[j])
        {
            if(j!=0)
            {
                j = lps[j-1];
            }
            else{
                i++;
            }
        }

    }

}

int main()
{
    cout<<"Enter text : ";
    cin>>txt;
    cout<<"Enter pattern : ";
    cin>>pat;
    mem(lps, 0);
    kmp();
    buildLps();
    for(int i=0; i<pat.size(); i++)printf("%d ",lps[i]);
    printf("\n");

}