Find the longest proper prefix that is also a suffix

Efficient Approach

Prerequisite: KMP Algorithm

In the KMP string matching algorithm, we calculate the LPS array such that LPS[i] denotes the longest proper prefix that is also a suffix of the substring ending at index ‘i’. We can use the same approach to calculate the LPS array. Our final answer will be LPS[n-1].

Steps to calculate LPS array:

1. Initialize the LPS array of size ‘N’, where ‘N’ is the size of the input string and set ‘LPS[i]’=0 for 0 <= ‘i’ < ‘N’.
2. We will maintain a variable ‘prev’, which denotes the last longest proper prefix which was also a suffix.
3. We iterate from index 1 to ‘N’-1, and consider the substring ending at that index.
4. If ‘S[i]’ equals ‘S[prev]’, we increment the current and previous indexes and update ‘LPS[i]’ as prev+1.
5. If they don’t match:
   1. If ‘prev’ is equal to 0, we set LPS[i]=0. This means that no suffix ends at index ‘i’ and is a proper prefix.
   2. Else, we set ‘prev’ = ‘LPS[prev-1]’.

Implementation

#include<bits/stdc++.h>
using namespace std;
 
// Function to calculate LPS array
vector<int> getLps(string pat){
    int m = pat.size();
 
    // Vector to store the LPS array.
    vector<int>lps(m);
 
    /*
    Prev is the last longest proper prefix
    which is also a suffix
    */
    int prev = 0;
    int ind = 1;
    while (ind < m){
 
        // If both are equal
        if (pat[ind]==pat[prev]){
            prev++;
            lps[ind]=prev;
            ind++;
        }
 
        // If the current elements are unequal and LPS is 0
        else if (prev==0){
            lps[ind]=0;
            ind++;
        }
 
        // If the current elements are unequal but LPS is not 0
        else{
            prev = lps[prev-1];
        }
    }
    return lps;
}

/*
Function to find the length of the
Longest proper prefix that is also a suffix
*/
void solve(string s){
   
    // Calculating LPS array of the input string
    vector<int> lps = getLps(s);

    // Printing LPS[n-1].
    cout<<lps[s.size() - 1]<<endl;
}

// Driver Code
int main()
{
    string s = "xyxyxy";
    solve(s);
}

Output

4

Time Complexity: O(N)

To generate the LPS array, we are using a while loop. Let us analyze the number of iterations the while loop will take. In each case, in the while loop, either we increment the current index by 1 or keep it the same. Whenever we keep it the same, we decrement ‘prev’ by at least 1. This means that the case when the current index is not incremented will occur at max ‘N’ times for the whole string. In the remaining iterations, the current index value will be incremented by 1, so the total iterations of the while loop will be O(N). Therefore, the time complexity of the above approach is O(N).

Space Complexity: O(N)

We have created a new LPS array of size N. Therefore, the space complexity of the approach is O(N).

Also see, Morris Traversal for Inorder.

FAQs

1. What is the use of the KMP algorithm?
   The KMP algorithm is used to find patterns in long strings. It can be used to search a substring in a string, find the number of unique substrings in a string, find all occurrences of the pattern in the string, etc.
    
2. What are other similar algorithms?
   Z Algorithm also searches for the given pattern in the string. Both these algorithms have the same space and time complexity, but the Z algorithm is simpler to understand. There is another algorithm called Rabin Karp, which uses O(1) space.
    
3. What is the LPS array?
   LPS stands for Longest proper Prefix, which is also a Suffix. As the name suggests, LPS[i] stores the longest proper prefix, also a suffix for the substring ending at index i. A string's proper prefix is any other than the entire string itself.

Key Takeaways

In this article, we discussed finding the longest proper prefix that is also a suffix for the given string. We also discussed the time and space complexity of our solution. If you want to solve more such problems, you can visit Coding Ninjas Studio.

Check out this problem - Longest Common Prefix

If you think that this blog helped you share it with your friends!. To be more confident in data structures and algorithms, try out our DS and Algo Course.

Until then, All the best for your future endeavors, and Keep Coding.