KMP_Implementation

#include <bits/stdc++.h>
#include <stdio.h>

using namespace std;

vector<int> createLPS(string pattern);
void kmp(string text, string pattern);

int main()
{
    int t;
    cout<<"Enter Number of Test Case: ";
    cin>>t; getchar();
    while(t--)
    {
        string pattern, text;
        getline(cin, text);
        getline(cin, pattern);
        kmp(text, pattern);
    }

    return 0;
}

//refer to Fig. 17 for visualization
vector<int> createLPS(string pattern)
{
    vector<int> LPS(pattern.length());
    int index = 0; //pointing to the beginning of pattern

    // Parsing the pattern
       // index will always follow i and i will be incremented if there is a match
    for(int i = 1; i < pattern.length();)
    {
        if(pattern[index] == pattern[i])
        {
            LPS[i] = index + 1; //because found match on i
            index++; i++; //if matches, increase both index and i
        }

        else
        {
            //if no match, decrease look at the previous LPS value and
            //set it to the present index.
            if(index != 0) //holding the index inside the array.
                index = LPS[index - 1];
            else
                {   //index 0 means we can not decrease
                                        //rather assign the 0 value to LPS[i]
                    LPS[i] = index ;
                    //since we can not match any more, we take i to one step right.
                    i++;
                }

        }

    }

    return LPS;
}


void kmp(string text, string pattern)
{
    //first the LPS table is needed as seen in the Example
    vector<int> LPS = createLPS(pattern);
    bool flag = false;
    int i = 0, j = 0;
    // i for text, j for pattern, recall in the example we said we can also
    //return the position of occurrence in the text, i will help in this matter.

    //Parsing the text
    while(i<text.length())
    {
        if(text[i]==pattern[j]) //recalling the green cells in the example
        {
            i++, j++; //advancing forward, can bee seen in Fig. 12
        }


        else //for mismatch, LPS table comes into the picture
        {
            if(j!=0)     // we need to consult the LPS table, refer to Fig 12 for this scenario
                j=LPS[j-1];
            else
            //for j=0 in mismatch see the Fig. 11 and 15,
            //we can not match anymore so we go right in the text.
                i++;
        }

        //If we reach the end of the pattern then we have found the pattern
        if (j==pattern.length()) //the last match will make j equal to pattern length
        {
            //cout << "OCCURANCE FOUND" << endl;
            //adding 1 for convenience of the user
            cout<<"POSITION OF OCCURRENCE: "<< i-pattern.length()+1<<endl;
            flag=true;
            j=LPS[j-1]; // we look for multiple occurrences
        }

    }

    if(!flag) cout<<"NO OCCURRENCE FOUND"<<endl;

}