#include<bits/stdc++.h>

using namespace std;

int n,m;
int LPS[50];

void ComputePrefixFn(char* p)
{
    m = strlen(p);
    LPS[0]=0;
    int k=0;

    for(int q=1;q<m;q++)
    {
        while(k>0 && p[k]!=p[q])
            k=LPS[k-1];
        if(p[k]==p[q])
            k++;
            LPS[q]=k;
    }
}


void KMP_Matcher(char* t,char* p)
{
    n =strlen(t);
    ComputePrefixFn(p);
    int q=0;
    for(int i=0;i<n;i++)
    {
        while(q>0 && p[q]!=t[i])
            q=LPS[q-1];
        if(p[q]==t[i])
            q++;
        if(q==m)
        {
            cout<<"Pattern occurs with shift "<<i-m+1<<endl;
            q=LPS[q-1];
        }
    }
}


int main()
{
    char t[10];
    char p[10];
    cout<<"INPUT STRING:";
    cin>>t;
    cout<<"INPUT pattern:";
    cin>>p;
    KMP_Matcher(t,p);
}