Longest prefix which is also suffix

Read

Discuss(40+)

Given a string s, find the length of the longest prefix, which is also a suffix. The prefix and suffix should not overlap.

Examples:

Input : S = aabcdaabc
Output : 4
Explanation: The string “aabc” is the longest prefix which is also suffix.

Input : S = abcab
Output : 2

Input : S = aaaa
Output : 2

Naive approach:

Since overlapping prefixes and suffixes is not allowed, we break the string from the middle and start matching left and right strings. If they are equal return size of one string, else they try for shorter lengths on both sides.

Below is a solution to the above approach:

C++

// CPP program to find length of the
// longest prefix which is also suffix
#include <bits/stdc++.h>
using namespace std;
 
// Function to find largest prefix
// which is also a suffix
int largest_prefix_suffix(const std::string& str)
{
    int n = str.length();
 
    // If the length of the string is less than 2, there
    // can't be a non-overlapping prefix and suffix, so
    // return 0.
    if (n < 2) {
        return 0;
    }
 
    // Initialize the length of the longest prefix which is
    // also a suffix.
    int len = 0;
    int i = 0;
 
    // Iterate through the first half of the string.
    while (i < n / 2) {
        int j1 = 0, j2 = (n - 1) - i;
        int isPrefixSuffix = 1;
 
        // Check if characters at corresponding positions in
        // the first half (j1) and the second half (j2) of
        // the string are equal.
        while (j1 <= i) {
 
            // If any pair of characters doesn't match, it's
            // not a prefix-suffix.
            if (str[j1] != str[j2]) {
                isPrefixSuffix = 0;
            }
            j1++;
            j2++;
        }
 
        // If it's a prefix-suffix, update the length.
        if (isPrefixSuffix == 1)
            len = i + 1;
        i++;
    }
 
    // Return the length of the longest prefix which is also
    // a suffix.
    return len;
}
 
// Driver code
int main()
{
    string s = "blablabla";
 
    // Function Call to find the length of the longest
    // prefix which is also a suffix
    cout << largest_prefix_suffix(s);
 
    return 0;
}

Java

public class LongestPrefixSuffix {
    // Function to find the length of the longest prefix
    // which is also a suffix
    public static int largestPrefixSuffix(String str)
    {
        int n = str.length();
 
        // If the length of the string is less than 2, there
        // can't be a non-overlapping prefix and suffix, so
        // return 0.
        if (n < 2) {
            return 0;
        }
 
        // Initialize the length of the longest
        // prefix which is also a suffix.
        int len = 0;
       
        int i = 0;
 
        // Iterate through the first half of the string.
        while (i < n / 2) {
            int j1 = 0, j2 = (n - 1) - i;
            boolean isPrefixSuffix = true;
 
            // Check if characters at corresponding
            // positions in the first half (j1) and the
            // second half (j2) of the string are equal.
            while (j1 <= i) {
 
                // If any pair of characters doesn't match,
                // it's not a prefix-suffix.
                if (str.charAt(j1) != str.charAt(j2)) {
                    isPrefixSuffix = false;
                }
                j1++;
                j2++;
            }
            // If it's a prefix-suffix, update the length.
            if (isPrefixSuffix)
                len = i + 1;
            i++;
        }
 
        // Return the length of the longest prefix which is
        // also a suffix.
        return len;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String s = "blablabla";
 
        // Function Call to find the length of the longest
        // prefix which is also a suffix
        System.out.println(largestPrefixSuffix(s));
    }
}

Python3

# Function to find the length of the longest prefix which is also a suffix
def largest_prefix_suffix(s):
    n = len(s)
 
    # If the length of the string is less than 2, there can't be a non-overlapping
    # prefix and suffix, so return 0.
    if n < 2:
        return 0
    lenn = 0  # Initialize the length of the longest prefix which is also a suffix.
    i = 0
 
    # Iterate through the first half of the string.
    while i < n // 2:
        j1 = 0
        j2 = (n - 1) - i
        is_prefix_suffix = True
 
        # Check if characters at corresponding positions in the first half (j1)
        # and the second half (j2) of the string are equal.
        while j1 <= i:
            if s[j1] != s[j2]:
                is_prefix_suffix = False  # If any pair of characters doesn't match, it's not a prefix-suffix.
            j1 += 1
            j2 += 1
        if is_prefix_suffix:
            lenn = i + 1  # If it's a prefix-suffix, update the length.
        i += 1
 
    # Return the length of the longest prefix which is also a suffix.
    return lenn
 
# Driver code
s = "blablabla"
# Function Call to find the length of the longest prefix which is also a suffix
print(largest_prefix_suffix(s))

C#

using System;
 
class Program {
    // Function to find the length of the longest prefix
    // which is also a suffix
    static int LargestPrefixSuffix(string str)
    {
        int n = str.Length;
 
        // If the length of the string is less than 2, there
        // can't be a non-overlapping prefix and suffix, so
        // return 0.
        if (n < 2) {
            return 0;
        }
        int len = 0; // Initialize the length of the longest
                     // prefix which is also a suffix.
        int i = 0;
 
        // Iterate through the first half of the string.
        while (i < n / 2) {
            int j1 = 0;
            int j2 = (n - 1) - i;
            bool isPrefixSuffix = true;
 
            // Check if characters at corresponding
            // positions in the first half (j1) and the
            // second half (j2) of the string are equal.
            while (j1 <= i) {
                if (str[j1] != str[j2]) {
                    isPrefixSuffix
                        = false; // If any pair of
                                 // characters doesn't
                                 // match, it's not a
                                 // prefix-suffix.
                }
                j1++;
                j2++;
            }
            if (isPrefixSuffix)
                len = i + 1; // If it's a prefix-suffix,
                             // update the length.
            i++;
        }
 
        // Return the length of the longest prefix which is
        // also a suffix.
        return len;
    }
 
    // Driver code
    static void Main()
    {
        string s = "blablabla";
 
        // Function Call to find the length of the longest
        // prefix which is also a suffix
        Console.WriteLine(LargestPrefixSuffix(s));
    }
}

Javascript

// Function to find the length of the longest prefix which is also a suffix
function largestPrefixSuffix(str) {
    const n = str.length;
 
    // If the length of the string is less than 2, there can't be a non-overlapping
    // prefix and suffix, so return 0.
    if (n < 2) {
        return 0;
    }
    let len = 0; // Initialize the length of the longest prefix which is also a suffix.
    let i = 0;
 
    // Iterate through the first half of the string.
    while (i < Math.floor(n / 2)) {
        let j1 = 0;
        let j2 = (n - 1) - i;
        let isPrefixSuffix = true;
 
        // Check if characters at corresponding positions in the first half (j1)
        // and the second half (j2) of the string are equal.
        while (j1 <= i) {
            if (str.charAt(j1) !== str.charAt(j2)) {
                isPrefixSuffix = false; // If any pair of characters doesn't match, it's not a prefix-suffix.
            }
            j1++;
            j2++;
        }
        if (isPrefixSuffix) {
            len = i + 1; // If it's a prefix-suffix, update the length.
        }
        i++;
    }
 
    // Return the length of the longest prefix which is also a suffix.
    return len;
}
 
// Driver code
const s = "blablabla";
 
// Function Call to find the length of the longest prefix which is also a suffix
console.log(largestPrefixSuffix(s));

Output

Time Complexity: O(n^2)
Auxiliary Space: O(1)

Longest prefix which is also suffix using KMP algorithm:

The idea is to use the preprocessing algorithm KMP search. In the preprocessing algorithm, we build lps array which stores the following values.

lps[i] = the longest proper prefix of pat[0..i]
which is also a suffix of pat[0..i].

Below is the implementation:

C++

// Efficient CPP program to find length of 
// the longest prefix which is also suffix
#include<bits/stdc++.h>
using namespace std;
 
// Returns length of the longest prefix
// which is also suffix and the two do
// not overlap. This function mainly is
// copy computeLPSArray() of in below post
// https://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
int longestPrefixSuffix(string s)
{
    int n = s.length();
 
    int lps[n];
    lps[0] = 0; // lps[0] is always 0
 
    // length of the previous
    // longest prefix suffix
    int len = 0;
 
    // the loop calculates lps[i]
    // for i = 1 to n-1
    int i = (n+1)/2;
    while (i < n)
    {
        if (s[i] == s[len])
        {
            len++;
            lps[i] = len;
            i++;
        }
        else // (pat[i] != pat[len])
        {
            // This is tricky. Consider
            // the example. AAACAAAA
            // and i = 7. The idea is
            // similar to search step.
            if (len != 0)
            {
                len = lps[len-1];
 
                // Also, note that we do
                // not increment i here
            }
            else // if (len == 0)
            {
                lps[i] = 0;
                i++;
            }
        }
    }
 
    int res = lps[n-1];
 
    // Since we are looking for
    // non overlapping parts.
    return res;
}
 
// Driver program to test above function
int main()
{
    string s = "bbabbabb";
    cout << longestPrefixSuffix(s);
    return 0;
}
 
// Corrected by Nilanshu Yadav

C

#include <stdio.h>
#include <string.h>
 
int longestPrefixSuffix(const char* s)
{
    int n = strlen(s);
    int lps[n];
    lps[0] = 0; // lps[0] is always 0
 
    int len = 0;
    int i = (n + 1) / 2;
 
    while (i < n) {
        if (s[i] == s[len]) {
            len++;
            lps[i] = len;
            i++;
        }
        else {
            if (len != 0) {
                len = lps[len - 1];
            }
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
 
    int res = lps[n - 1];
 
    return res;
}
 
int main()
{
    const char* s = "bbabbabb";
    printf("%d\n", longestPrefixSuffix(s));
    return 0;
}

Java

// Efficient Java program to find length of 
// the longest prefix which is also suffix
 
class GFG 
{
    // Returns length of the longest prefix
    // which is also suffix and the two do
    // not overlap. This function mainly is
    // copy computeLPSArray() of in below post
    // https://www.geeksforgeeks.org/searching-
    // for-patterns-set-2-kmp-algorithm/
    static int longestPrefixSuffix(String s)
    {
        int n = s.length();
     
        int lps[] = new int[n];
         
        // lps[0] is always 0
        lps[0] = 0; 
     
        // length of the previous
        // longest prefix suffix
        int len = 0;
     
        // the loop calculates lps[i]
        // for i = 1 to n-1
        int i = (n+1)/2;
        while (i < n)
        {
            if (s.charAt(i) == s.charAt(len))
            {
                len++;
                lps[i] = len;
                i++;
            }
             
             // (pat[i] != pat[len])
            else
            {
                // This is tricky. Consider
                // the example. AAACAAAA
                // and i = 7. The idea is
                // similar to search step.
                if (len != 0)
                {
                    len = lps[len-1];
     
                    // Also, note that we do
                    // not increment i here
                }
                 
                // if (len == 0)
                else
                {
                    lps[i] = 0;
                    i++;
                }
            }
        }
     
        int res = lps[n-1];
     
        // Since we are looking for
        // non overlapping parts.
        return res;
    }
     
    // Driver program 
    public static void main (String[] args) 
    {
        String s = "bbabbabb";
        System.out.println(longestPrefixSuffix(s));
    }
}
 
// This code is contributed by Anant Agarwal.
// Corrected by Nilanshu Yadav

Python3

# Efficient Python 3 program
# to find length of 
# the longest prefix 
# which is also suffix
 
# Returns length of the longest prefix
# which is also suffix and the two do
# not overlap. This function mainly is
# copy computeLPSArray() of in below post
# https://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
def longestPrefixSuffix(s) :
    n = len(s)
    lps = [0] * n   # lps[0] is always 0
  
    # length of the previous
    # longest prefix suffix
    l = 0
     
    # the loop calculates lps[i]
    # for i = 1 to n-1
    i = (n+1)//2;
    while (i < n) :
        if (s[i] == s[l]) :
            l = l + 1
            lps[i] = l
            i = i + 1
         
        else :
 
            # (pat[i] != pat[len])
            # This is tricky. Consider
            # the example. AAACAAAA
            # and i = 7. The idea is
            # similar to search step.
            if (l != 0) :
                l = lps[l-1]
  
                # Also, note that we do
                # not increment i here
             
            else :
 
                # if (len == 0)
                lps[i] = 0
                i = i + 1
  
    res = lps[n-1]
  
    # Since we are looking for
    # non overlapping parts.
    return res;
         
  
# Driver program to test above function
s = "bbabbabb"
print(longestPrefixSuffix(s))
 
 
# This code is contributed
# by Nikita Tiwari.
#Corrected by Nilanshu Yadav

C#

// Efficient C# program to find length of 
// the longest prefix which is also suffix
using System;
 
class GFG {
     
    // Returns length of the longest prefix
    // which is also suffix and the two do
    // not overlap. This function mainly is
    // copy computeLPSArray() of in below post
    // https://www.geeksforgeeks.org/searching-
    // for-patterns-set-2-kmp-algorithm/
    static int longestPrefixSuffix(string s)
    {
        int n = s.Length;
     
        int []lps = new int[n];
         
        // lps[0] is always 0
        lps[0] = 0; 
     
        // length of the previous
        // longest prefix suffix
        int len = 0;
     
        // the loop calculates lps[i]
        // for i = 1 to n-1
        int i = 1;
        while (i < n)
        {
            if (s[i] == s[len])
            {
                len++;
                lps[i] = len;
                i++;
            }
             
            // (pat[i] != pat[len])
            else
            {
                 
                // This is tricky. Consider
                // the example. AAACAAAA
                // and i = 7. The idea is
                // similar to search step.
                if (len != 0)
                {
                    len = lps[len-1];
     
                    // Also, note that we do
                    // not increment i here
                }
                 
                // if (len == 0)
                else
                {
                    lps[i] = 0;
                    i++;
                }
            }
        }
     
        int res = lps[n-1];
     
        // Since we are looking for
        // non overlapping parts.
        return (res > n/2) ? n/2 : res;
    }
     
    // Driver program 
    public static void Main () 
    {
        string s = "abcab";
         
        Console.WriteLine(longestPrefixSuffix(s));
    }
}
 
// This code is contributed by vt_m.

Javascript

<script>
 
// Efficient javascript program to find length of 
// the longest prefix which is also suffix{
// Returns length of the longest prefix
// which is also suffix and the two do
// not overlap. This function mainly is
// copy computeLPSArray() of in below post
// https://www.geeksforgeeks.org/searching-
// for-patterns-set-2-kmp-algorithm/
function longestPrefixSuffix(s)
{
    var n = s.length;
 
    var lps = Array.from({length: n}, (_, i) => 0);
     
    // lps[0] is always 0
    lps[0] = 0; 
 
    // length of the previous
    // longest prefix suffix
    var len = 0;
 
    // the loop calculates lps[i]
    // for i = 1 to n-1
    var i = 1;
    while (i < n)
    {
        if (s.charAt(i) == s.charAt(len))
        {
            len++;
            lps[i] = len;
            i++;
        }
         
         // (pat[i] != pat[len])
        else
        {
            // This is tricky. Consider
            // the example. AAACAAAA
            // and i = 7. The idea is
            // similar to search step.
            if (len != 0)
            {
                len = lps[len-1];
 
                // Also, note that we do
                // not increment i here
            }
             
            // if (len == 0)
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
 
    var res = lps[n-1];
 
    // Since we are looking for
    // non overlapping parts.
    return (res > n/2)? n/2 : res;
}
 
// Driver program 
var s = "abcab";
document.write(longestPrefixSuffix(s));
 
 
// This code is contributed by 29AjayKumar 
 
 
</script>

PHP

<?php
// Efficient PHP program to find length of 
// the longest prefix which is also suffix
 
// Returns length of the longest prefix
// which is also suffix and the two do
// not overlap. This function mainly is
// copy computeLPSArray() of in below post
// https://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
function longestPrefixSuffix($s)
{
    $n = strlen($s);
 
    $lps[$n] = NULL;
     
    // lps[0] is always 0
    $lps[0] = 0; 
 
    // length of the previous
    // longest prefix suffix
    $len = 0;
 
    // the loop calculates lps[i]
    // for i = 1 to n-1
    $i = 1;
    while ($i < $n)
    {
        if ($s[$i] == $s[$len])
        {
            $len++;
            $lps[$i] = $len;
            $i++;
        }
         
        // (pat[i] != pat[len])
        else
        {
             
            // This is tricky. Consider
            // the example. AAACAAAA
            // and i = 7. The idea is
            // similar to search step.
            if ($len != 0)
            {
                $len = $lps[$len-1];
 
                // Also, note that we do
                // not increment i here
            }
             
            // if (len == 0)
            else
            {
                $lps[$i] = 0;
                $i++;
            }
        }
    }
 
    $res = $lps[$n-1];
 
    // Since we are looking for
    // non overlapping parts.
    return ($res > $n/2)? $n/2 : $res;
}
 
    // Driver Code
    $s = "abcab";
    echo longestPrefixSuffix($s);
 
// This code is contributed by nitin mittal
?>

Output

Time Complexity: O(n)
Auxiliary Space: O(n)

Please refer computeLPSArray() of KMP search for an explanation.

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!