Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm.cpp

#include <bits/stdc++.h>

#define MEM(a,b) memset((a),(b),sizeof(a))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIn(a,b) ((a)<(b)?(a):(b))
#define MIn4(a,b,c,d) MIn(MIn(MIn(a,b),c),d)
#define In freopen("In.txt", "r", stdin);
#define Out freopen("out.txt", "w", stdout);

#define i64 long long
#define u64 long long unsigned

#define sz 1000

using namespace std;

string str,pattern;
int pi[sz];

void prefix()
{
    //Calculating the prefix

    int now;
    int len = pattern.size();
    pi[0] = now = -1;
    for(int i=1;i<len;i++)
    {
        while(now!=-1 && pattern[now+1]!=pattern[i])
            now = pi[now];
        if(pattern[now+1]==pattern[i]) pi[i] = ++now;
        else pi[i] = now = -1;
    }
}

int kmp()
{
    //checking for a substring
    //if pattern is a substring of str then this function
    //will return 1 else will return 1

    int now = -1;
    int sLen = str.size();
    int m = pattern.size();
    for(int i=0;i<sLen;i++)
    {
        while(now!=-1 && pattern[now+1]!=str[i])
            now = pi[now];
        if(pattern[now+1] == str[i]) ++now;
        else now = -1;
        if(now+1 == m)
            return 1;
    }
    return 0;
}

int main()
{
    //reading two string from user
    //"str" @base string
    //"pattern" @substring component

    //kmp() function return 1 if pattern is a substring of str
    //kmp() function return 0 if pattern is not a substring of str

    cin >> str >> pattern;
    prefix();
    cout << kmp() << endl;
}