Home » Interview coding problems/challenges

# 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

*represent the current index*

**lps***upto that index comparison, initialize*

**lps***, since it is not possible to have proper prefix-suffix with one letter then we declare two variable*

**lps[0]=0***and*

**j***by which we compare the characters.*

**i****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!