Longest prefix which is also suffix
Last Updated :
29 Mar, 2024
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++
#include <bits/stdc++.h>
using namespace std;
int largest_prefix_suffix(const std::string& str)
{
int n = str.length();
if (n < 2) {
return 0;
}
int len = 0;
int i = 0;
while (i < n / 2) {
int j1 = 0, j2 = (n - 1) - i;
int isPrefixSuffix = 1;
while (j1 <= i) {
if (str[j1] != str[j2]) {
isPrefixSuffix = 0;
}
j1++;
j2++;
}
if (isPrefixSuffix == 1)
len = i + 1;
i++;
}
return len;
}
int main()
{
string s = "blablabla";
cout << largest_prefix_suffix(s);
return 0;
}
|
Java
public class LongestPrefixSuffix {
public static int largestPrefixSuffix(String str)
{
int n = str.length();
if (n < 2) {
return 0;
}
int len = 0;
int i = 0;
while (i < n / 2) {
int j1 = 0, j2 = (n - 1) - i;
boolean isPrefixSuffix = true;
while (j1 <= i) {
if (str.charAt(j1) != str.charAt(j2)) {
isPrefixSuffix = false;
}
j1++;
j2++;
}
if (isPrefixSuffix)
len = i + 1;
i++;
}
return len;
}
public static void main(String[] args)
{
String s = "blablabla";
System.out.println(largestPrefixSuffix(s));
}
}
|
Python3
def largest_prefix_suffix(s):
n = len(s)
if n < 2:
return 0
lenn = 0
i = 0
while i < n // 2:
j1 = 0
j2 = (n - 1) - i
is_prefix_suffix = True
while j1 <= i:
if s[j1] != s[j2]:
is_prefix_suffix = False
j1 += 1
j2 += 1
if is_prefix_suffix:
lenn = i + 1
i += 1
return lenn
s = "blablabla"
print(largest_prefix_suffix(s))
|
C#
using System;
class Program {
static int LargestPrefixSuffix(string str)
{
int n = str.Length;
if (n < 2) {
return 0;
}
int len = 0;
int i = 0;
while (i < n / 2) {
int j1 = 0;
int j2 = (n - 1) - i;
bool isPrefixSuffix = true;
while (j1 <= i) {
if (str[j1] != str[j2]) {
isPrefixSuffix
= false;
}
j1++;
j2++;
}
if (isPrefixSuffix)
len = i + 1;
i++;
}
return len;
}
static void Main()
{
string s = "blablabla";
Console.WriteLine(LargestPrefixSuffix(s));
}
}
|
Javascript
function largestPrefixSuffix(str) {
const n = str.length;
if (n < 2) {
return 0;
}
let len = 0;
let i = 0;
while (i < Math.floor(n / 2)) {
let j1 = 0;
let j2 = (n - 1) - i;
let isPrefixSuffix = true;
while (j1 <= i) {
if (str.charAt(j1) !== str.charAt(j2)) {
isPrefixSuffix = false;
}
j1++;
j2++;
}
if (isPrefixSuffix) {
len = i + 1;
}
i++;
}
return len;
}
const s = "blablabla";
console.log(largestPrefixSuffix(s));
|
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++
#include<bits/stdc++.h>
using namespace std;
int longestPrefixSuffix(string str)
{
vector<int> A(str.size(), 0);
int j = 0, i = 1;
while(i < str.size())
{
if(str[i] == str[j])
{
A[i] = j+1;
j++;
i++;
}
else
{
if(j==0)
i++;
else
j = A[j-1];
}
}
return A.back();
}
int main()
{
string s = "abadabab";
cout << longestPrefixSuffix(s);
return 0;
}
|
Java
class GFG
{
static int longestPrefixSuffix(String str)
{
int[] A = new int[str.length()];
int j = 0, i = 1;
while(i < str.length())
{
if(str.charAt(i) == str.charAt(j))
{
A[i] = j+1;
j++;
i++;
}
else
{
if(j==0)
i++;
else
j = A[j-1];
}
}
return A[str.length()-1];
}
public static void main (String[] args)
{
String s = "bbabbabb";
System.out.println(longestPrefixSuffix(s));
}
}
|
Python3
def longestPrefixSuffix(str):
A = [0 for i in range(len(str))]
j = 0
i = 1
while i < len(str):
if str[i] == str[j]:
A[i] = j+1
j += 1
i += 1
else:
if j == 0:
i += 1
else:
j = A[j-1]
return A[-1]
s = "bbabbabb"
print(longestPrefixSuffix(s))
|
C#
using System;
class GFG {
static int longestPrefixSuffix(string s)
{
int n = s.Length;
int []lps = new int[n];
lps[0] = 0;
int len = 0;
int i = 1;
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 > n/2) ? n/2 : res;
}
public static void Main ()
{
string s = "abcab";
Console.WriteLine(longestPrefixSuffix(s));
}
}
|
Javascript
<script>
function longestPrefixSuffix(str)
{
let A = new Array(s.length).fill(0);
let j = 0, i = 1;
while(i < s.length)
{
if(s[i] == s[j])
{
A[i] = j+1;
j++;
i++;
}
else
{
if(j==0)
i++;
else
j = A[j-1];
}
}
return A[A.length - 1];
}
var s = "abcab";
document.write(longestPrefixSuffix(s));
</script>
|
PHP
<?php
function longestPrefixSuffix($s)
{
$n = strlen($s);
$lps[$n] = NULL;
$lps[0] = 0;
$len = 0;
$i = 1;
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++;
}
}
}
$res = $lps[$n-1];
return ($res > $n/2)? $n/2 : $res;
}
$s = "abcab";
echo longestPrefixSuffix($s);
?>
|
Time Complexity: O(n)
Auxiliary Space: O(n)
Please refer computeLPSArray() of KMP search for an explanation.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...