Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem
1.1.
Examples
2.
Naive Approach
2.1.
Implementation
2.1.1.
Time Complexity: O(N ^ 2)
2.1.2.
Space Complexity: O(N)
3.
Efficient Approach
3.1.
Implementation
3.1.1.
Output
3.1.2.
Time Complexity: O(N)
3.1.3.
Space Complexity: O(N)
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Find the longest proper prefix that is also a suffix

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Problem

Given a string ‘S’, find the longest proper prefix that is also a suffix of ‘S’. You have to print the size of the longest proper prefix.

Note: A string’s proper prefix includes all prefixes except the entire string itself.

Examples

Input: ‘S’ = xyxyxy

Output: 4

Explanation:

The prefix of length 4 is ‘xyxy’, and the suffix of length 4 is ‘xyxy’. Therefore the prefix of length 4 is valid. If we take a length equal to 5, the prefix will be ‘xyxyx’ while the suffix will be ‘yxyxy’. These are not equal, so the prefix of length 5 is not valid. We can’t take a prefix of length 6, as that will contain the entire string (it will not be a proper prefix).

Therefore, the longest proper prefix that is also a suffix has length 4.

 

Input: ‘S’ = abcab

Output: 2

Explanation:

The longest proper prefix that is also a suffix for the above example is ‘ab’.

Naive Approach

We can iterate over the length of the proper prefix and check if it matches the suffix of the same length. If it matches, we will update our answer. Thus, in the end, we will get the length of the longest proper prefix that is also a suffix.

Implementation

#include<bits/stdc++.h>
#define ll long long
using namespace std;

/*
Function to find the length of
Longest proper prefix that is also a suffix.
*/
void solve(string s){

    int ans = 0;
    int n = s.size();

    // Iterating over the length of prefix
    for (int l = 1; l<=n-1; l++){
        string prefix = "";
        string suffix = "";

        // Storing prefix of the given length
        for(int i=0; i<l; i++){
            prefix += s[i];
        }

        // Storing suffix of the given length
        for(int i=n-l; i<n; i++){
            suffix += s[i];
        }

        // If prefix and suffix are same, update answer
        if (prefix == suffix){
            ans = l;
        }
    }

    // Printing the longest proper prefix that is also a suffix.
    cout<<ans<<endl;
}

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

Output:

4

Time Complexity: O(N ^ 2)

We are first iterating over the length of the prefix, which will take O(N) time. For each length value, we create corresponding prefixes and suffixes and check if they are equal. This will again take O(N) time. Therefore the total time complexity of the above approach is O(N ^ 2).

Space Complexity: O(N)

For each value of the length of the prefix, we are creating a corresponding prefix and suffix. This will take O(N) space. Therefore, the space complexity of the above approach is O(N).

Also check out - Substr C++ and Rabin Karp Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

Previous article
Minimum Repetitions of String A, to Generate String B as its Substring
Next article
Count Valleys
Live masterclass