Strings: Longest Prefix Suffix

Problem Statement:

You are given a string, you need to find the length of longest proper perfix which is also a suffix.

Example

Example 1:

str = “abcdabc”

Output:
3

Here “abc” is the longest prefix suffix

Example 2:

str = “abcdef

Output:
3

Here there is no prefix that is also suffix

Solution

This problem can be solved in 2 different ways.

1. Brute Force Method

2. Optimized approach

1. Brute Force Method

In this approach we break the string in to two half from the mid point and start matching the left and right string.

If they are equal we return the size else we try for shorter lengths on both sides.

2. Optimized approach

Before we start with this approach, let us first understand what are valid prefix and suffix.

For a given string,
valid prefix are the all the prefix till the end of string -1.
valid suffix are the all the suffix till the starting of string -1.

Example:

String: abcd
Valid Prefix are: a, ab, abc
Valid Suffix are: d, cd, bcd

Now the Longest prefix suffix is the length of the common prefix and suffix.

Example Str = “aabaa”
LPS = 2 because “aa” is prefix and suffix.

Now coming to this approach:

In this approach, we will use a temp array that represents the length of the longest proper prefix and suffix in that array.

We take an temp array lps[] and it will store the length of a longest proper prefix that is equal to the suffix at each index of lps for str[0..i]

For example:

Str = “abacabad”

LPS = [ 0 0 1 0 1 2 3 0]

Reason:

For lps[0] = 0 because the length of proper prefix for single character is 0.
For lps[1] = 0 because “ab”, there is no prefix that is also suffix
For lps[2] = 1 because “aba”, the longest prefix which is also a suffix = “a”
For lps[3] = 0 because “abac”, there is no prefix that is also suffix.
For lps[4] = 1 because “abaca”, the longest prefix which is also a suffix = “a”
For lps[5] = 2 because “abacab”, the longest prefix which is also a suffix = “ab”
For lps[6] = 3 because “abacaba”, the longest prefix which is also a suffix = “aba”
For lps[7] = 0 there is no prefix that is also suffix.

So 0 is the result.

This is an example of KMP algorithm

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 
#include <queue> 

using namespace std;

int largest_prefix_suffix_brute_force(string &str) 
{ 
    
  int n = str.length(); 
    
  if(n < 2) { 
    return 0; 
  } 
  
  int len = 0; 
  int i = n/2; 
    
  while(i < n) 
  { 
    if(str[i] == str[len]) 
    { 
      ++len; 
      ++i; 
    } 
    else 
    { 
      if(len == 0) 
      {
        ++i; 
      } else { 
        --len; 
      } 
    } 
  } 
    
  return len; 
  
} 
  
int main() 
{ 
      
string s = "abacabad"; 
  
cout <<"The length using brute force = "<<largest_prefix_suffix_brute_force(s)<<endl; 
  
return 0; 
} 

Output:

The length using brute force = 0