Given a string s, find length of the longest prefix which is also suffix. The prefix and suffix should not overlap.
Examples:
Input : aabcdaabc Output : 4 The string "aabc" is the longest prefix which is also suffix. Input : abcab Output : 2 Input : aaaa Output : 2
Simple Solution : Since overlapping of prefix and suffix is not allowed, we break the string from middle 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.
Below is a solution of 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 (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) { // no prefix ++i; } else { // search for shorter prefixes --len; } } } return len; } // Driver code int main() { string s = "blablabla" ; cout << largest_prefix_suffix(s); return 0; } |
Java
// Java program to find length of the longest // prefix which is also suffix class GFG { static int longestPrefixSuffix(String s) { int n = s.length(); if (n < 2 ) { return 0 ; } int len = 0 ; int i = n/ 2 ; while (i < n) { if (s.charAt(i) == s.charAt(len)) { ++len; ++i; } else { if (len == 0 ) { // no prefix ++i; } else { // search for shorter prefixes --len; } } } return len; } // Driver code public static void main (String[] args) { String s = "blablabla" ; System.out.println(longestPrefixSuffix(s)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to find length # of the longest prefix which # is also suffix def longestPrefixSuffix(s) : n = len (s) for res in range (n / / 2 , 0 , - 1 ) : # Check for shorter lengths # of first half. prefix = s[ 0 : res] suffix = s[n - res: n] if (prefix = = suffix) : return res # if no prefix and suffix match # occurs return 0 s = "blablabla" print (longestPrefixSuffix(s)) # This code is contributed by Nikita Tiwari. |
C#
// C# program to find length of the longest // prefix which is also suffix using System; class GFG { static int longestPrefixSuffix(String s) { int n = s.Length; if (n < 2) return 0; int len = 0; int i = n / 2; while (i < n) { if (s[i] == s[len]) { ++len; ++i; } else { if (len == 0) { // no prefix ++i; } else { // search for shorter prefixes --len; } } } return len; } // Driver code public static void Main () { String s = "blablabla" ; Console.WriteLine(longestPrefixSuffix(s)); } } // This code is contributed by vt_m. |
3
Efficient Solution : The idea is to use preprocessing algorithm of KMP search. In the preprocessing algorithm, we build lps array which stores following values.
lps[i] = the longest proper prefix of pat[0..i]
which is also a suffix of pat[0..i].
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 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 = 1; 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 > n/2)? n/2 : res; } // Driver program to test above function int main() { string s = "abcab" ; cout << 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 // 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.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 > n/ 2 )? n/ 2 : res; } // Driver program public static void main (String[] args) { String s = "abcab" ; System.out.println(longestPrefixSuffix(s)); } } // This code is contributed by Anant Agarwal. |
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 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 = 1 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. if (res > n / 2 ) : return n / / 2 else : return res # Driver program to test above function s = "abcab" print (longestPrefixSuffix(s)) # This code is contributed # by Nikita Tiwari. |
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 // 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. |
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 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 ?> |
2
Please refer computeLPSArray() of KMP search for explanation.
Time Complexity : O(n)
Auxiliary Space : O(n)
leave a comment
0 Comments