Longest Prefix Suffix (KMP Algorithm)

 Longest Prefix Suffix (KMP Algo)

Given a string of characters, find the length of the longest proper prefix which is also a proper suffix.

Example:

Input: s = "abab"
Output: 2
Explanation: "ab" is the longest proper 
prefix and suffix.

Steps:

Make a array to store length of the matching prefix and Suffix  in order that the last entry will have the matched prefix and suffix length.

Solution:

int lps(string s)

{

    vector<int> A(s.size(), 0);

    int j = 0, i = 1;

    while (i < s.size())

    {

        if (s[i] == s[j])

        {

            A[i] = j + 1;

            j++;

            i++;

        }

        else

        {

            if (j == 0)

                i++;

            else

                j = A[j - 1];

        }

    }

    return A.back();

    // back() return last entry of the vector

}

Thank You.