SUBSTRING SEARCH - KMP ALGORITHM

KMP ALGORITHM : (Knuth Morris Pratt algorithm)

This is one of the most efficient string searching algorithms. This algorithm is a little bit difficult to understand. ( Don't Worry... I have included the link below where I referred to this algorithm from ).
Once you understand this algorithm, the coding part becomes very easy. I have found some good tutorials on youtube which explained me the concepts of KMP very clear.

 Given two strings pattern (P) and text(T). Find whether the pattern(P) is found in the text(T)

 The above problem when solved using naive algorithm gives a time complexity of O(M*N),
where M and N are the string lengths of the pattern and text.
             My brute force solution 
But the KMP algorithm solves this problem with a time complexity of  O(M+N).

Resources explaining this algorithm:
1. Youtube
2. Quora
3.GeeksforGeeks

       
#include<iostream>

using namespace std;

void construct_lps_array(int *lps_array,int M){



    int i = 1,k = 0;

    lps_array[0] = 0;

    /// constructing LPS array...

    while(i < M){

        if(lps_array[k] == lps_array[i]){

            k++;

            lps_array[i] = k;

            i++;

        }

        else{

            if(k != 0){

                k = lps_array[k-1];

            }

            else{

                lps_array[i] = 0;

                i++;

            }

        }

    }

}

void KMP_SEARCH(string text,string pattern,int N,int L){



    int lps_array[L];

    construct_lps_array(lps_array,L);

    int i=0,j=0;



    /// i is for text and j is for pattern....

    while(i < N){

        if(text[i] == pattern[j]){

            i++;

            j++;

        }

        if(j == L){

            cout << "The pattern is found at the postion "<<i-j<<"\n";

            //count++;

            j = lps_array[j-1];

        }

        else if(i<N && text[i] != pattern[j]){

            if(j == 0){

                i++;

            }

            else

                j = lps_array[j-1];

        }

    }

}

int main(){



    string text,pattern;

    cout << "Enter the text:";

    cin >> text;

    cout << "Enter the pattern:";

    cin >> pattern;

    int N = text.length();

    int L = pattern.length();

    KMP_SEARCH(text,pattern,N,L);

    return 0;



}