Longest Prefix and Suffix

Longest Prefix and Suffix: Here, we are going to find the solution of Longest Prefix and Suffix – The problem has been featured in interview/coding rounds of many top tech companies such as Amazon, Accolite, MakeMyTrip.
Submitted by Divyansh Jaipuriyar, on May 24, 2020

Problem statement:

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

Input:

First line is T number of test cases. Each test case has one line denoting the string of length less than 100000.

Output:

Print length of longest proper prefix which is also a proper suffix.

Examples:

    Input:	
    T = 1
    "abcdabc"
    
    Output: 
    3
    //as prefix "abc" is the longest proper prefix 
    //present in the string.

    Input:
    T = 1
    "abcdefghijklm"
    
    Output: 
    0
    //as there is no prefix which is a suffix.

    Input:
    T = 1
    "aaaaaaa"

    Output:
    6
    //as for proper prefix we can't have entire length 
    // as the prefix so only length possible is 6.

Solution Approach

1) Brute Force Approach

Since the longest proper prefix which is also a suffix cannot be equal to the entire length of the string because it can't overlap each other, so we break the string from mid-point and start matching left and right string. If they are equal return size of any one string else try for shorter lengths on both sides.

Pseudo Code:

void solve(string str)
{
    // declare two variable which will used for
    // comparing two halfs of the string.
    int i, j;
    //store length in len variable.
    int len = str.length();
    i = len / 2; // initialise right half.
    j = 0; // initialise left half.

    // check if the right index variable
    // is less than the length of the string.
    while (i < len) {
        // if the left half character is
        // equal to right half characet.
        is(str[i] == str[j])
        {
            // simply incres the pointers to compare next indexes.
            i++;
            j++;
            continue;
        }
        else
        {
            // if the left half character is at start index
            // and it is not equal to right half current
            // character then increase

            if (j == 0) { // right half index.
                i++;
            }
            else { //search for lesser length of the prefix.
                j--;
            }
        }
    }
    return j; //return length of prefix.
}

C++ Implementation:

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

typedef long long ll;

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter string: ";
        string str;
        cin >> str;

        ll len = str.length();
        // if length is less than one then
        // simply length of lps is 0.

        if (len <= 1) {
            cout << 0 << "\n";
        }
        else {
            ll i = len / 2; // initialise right half.
            ll j = 0; // initialise left half.
            
            // check if the right index variable is less
            // than the length of the string.
            while (i < len) {
                // if the left half character is equal to
                // right half characet.
                if (str[i] == str[j]) {
                    i++;
                    j++;
                }
                else {
                    // if the left half character is at start index
                    // and it is not equal to right half current
                    // character then increase right half index.
                    if (j == 0)
                        i++;
                    else
                        j--; // search for lesser length of the prefix
                }
            }
            cout << "Longest prefix-suffix length: ";
            cout << j << "\n";
        }
    }
    
    return 0;
}

Output

Enter number of test cases: 3
Enter string: abcdabc
Longest prefix-suffix length: 3
Enter string: abcdefghabcdefgh
Longest prefix-suffix length: 8
Enter string: abcdefgh
Longest prefix-suffix length: 0

2) Better approach: Using longest prefix-suffix array of KMP algorithm

Here we will use an array which represents the length of the longest proper prefix which is also equal to the suffix of the array.

Here we use lps[] array which stores the length of a longest proper prefix which is the equal suffix, each index of lps represent the current index lps upto that index comparison, initialize lps[0]=0, since it is not possible to have proper prefix-suffix with one letter then we declare two variable j and i by which we compare the characters.

Pseudo Code:

int longestprefix(string str)
{
    int len = str.length(); //len variable stores length of string.
    int lps[len]; //declare lps array.
    lps[0] = 0; //single charater case so length lps is 0.
    int i = 1; //initialise index for comparison from 1.
    int j = 0; //initial longest prefix suffix length.
    while (i < len) //check until i!=len of string.
    {
        //check current index character with character stored at j.
        if (str[i] == str[j]) {
            j++; //increase length by one.
            lps[i] = j; //lps for current index is equal to j
            i++; //move forward.
        }
        else //if str[i]!=str[j]
        {
            //we search for that index which character matches
            //with the current character at index i.
            if (j != 0) {
                j = lps[j - 1];
            }
            else {
                lps[i] = 0;
                i++;
            } //if j==0 then lps[i]=0.
        }
    }
    return lps[j - 1]; //return lcs of given string.
}

C++ Implementation:

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

typedef long long ll;

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter string: ";
        string str;
        cin >> str;

        ll len = str.length(); //len variable stores length of string.
        ll lps[len]; //declare lps array.
        lps[0] = 0; //single charater case so length lps is 0.
        ll i, j;
        i = 1; //initialise index for comparison from 1.
        j = 0; //initial longest prefix suffix length.

        while (i < len) //check until i!=len of string.
        {
            //check current index character with character stored at j.
            if (str[i] == str[j]) 
            {
                j++; //increase length by one.
                lps[i] = j; //lps for current index is equal to j
                i++; //move forward.
            }
            else //if str[i]!=str[j]
            {
                //we search for that index which character matches 
                //with the current character at index i.
                if (j != 0) 
                    j = lps[j - 1];
                else {
                    lps[i] = 0; //if j==0 then lps[i]=0.
                    i++; //move forward.
                }
            }
        }
        cout << "Maximum length of proper prefix-suffix: ";
        cout << lps[len - 1] << "\n";
    }

    return 0;
}

Output:

Enter number of test cases: 3
Enter string: abcdefgh
Maximum length of proper prefix-suffix: 0
Enter string: abcdabc
Maximum length of proper prefix-suffix: 3
Enter string: abcdefghabcdefgh            
Maximum length of proper prefix-suffix: 8
  • Time Complexity for above approach is: O(n)
  • Space Complexity for above approach is: O(n)

Problem reference: https://practice.geeksforgeeks.org/problems/longest-prefix-suffix/0






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.