Given string str, the task is to find the longest prefix which is also the suffix of the given string. The prefix and suffix should not overlap. If no such prefix exists then print -1.
Examples:
Input: str = “aabcdaabc”
Output: aabc
The string “aabc” is the longest
prefix which is also suffix.Input: str = “aaaa”
Output: aa
Approach: The idea is to use the pre-processing algorithm of the KMP search. In this 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].
We get the length using the above approach, then print the same number of characters from the front which is our answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#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 of computeLPSArray() in KMP Algorithmint LengthlongestPrefixSuffix(string s){ int n = s.length(); int lps[n]; // lps[0] is always 0 lps[0] = 0; // Length of the previous // longest prefix suffix int len = 0; // Loop to calculate 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 { // 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;}// Function that returns the prefixstring longestPrefixSuffix(string s){ // Get the length of the longest prefix int len = LengthlongestPrefixSuffix(s); // Stores the prefix string prefix = ""; // Traverse and add characters for (int i = 0; i < len; i++) prefix += s[i]; // Returns the prefix return prefix;}// Driver codeint main(){ string s = "abcab"; string ans = longestPrefixSuffix(s); if (ans == "") cout << "-1"; else cout << ans; return 0;} |
Java
// Java implementation of the approach class GfG { // Returns length of the longest prefix // which is also suffix and the two do // not overlap. This function mainly is // copy of computeLPSArray() in KMP Algorithm static int LengthlongestPrefixSuffix(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; // Loop to calculate 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++; } 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; } // Function that returns the prefix static String longestPrefixSuffix(String s) { // Get the length of the longest prefix int len = LengthlongestPrefixSuffix(s); // Stores the prefix String prefix = ""; // Traverse and add characters for (int i = 0; i < len; i++) prefix += s.charAt(i); // Returns the prefix return prefix; } // Driver code public static void main(String[] args) { String s = "abcab"; String ans = longestPrefixSuffix(s); if (ans == "") System.out.println("-1"); else System.out.println(ans); }} |
Python3
# Python 3 implementation of the approach# Returns length of the longest prefix# which is also suffix and the two do# not overlap. This function mainly is# copy of computeLPSArray() in KMP Algorithmdef LengthlongestPrefixSuffix(s): n = len(s) lps = [0 for i in range(n)] # Length of the previous # longest prefix suffix len1 = 0 # Loop to calculate lps[i] # for i = 1 to n - 1 i = 1 while (i < n): if (s[i] == s[len1]): len1 += 1 lps[i] = len1 i += 1 else: # This is tricky. Consider # the example. AAACAAAA # and i = 7. The idea is # similar to search step. if (len1 != 0): len1 = lps[len1 - 1] # Also, note that we do # not increment i here # If len = 0 else: lps[i] = 0 i += 1 res = lps[n - 1] # Since we are looking for # non overlapping parts if (res > int(n / 2)): return int(n / 2) else: return res# Function that returns the prefixdef longestPrefixSuffix(s): # Get the length of the longest prefix len1 = LengthlongestPrefixSuffix(s) # Stores the prefix prefix = "" # Traverse and add characters for i in range(len1): prefix += s[i] # Returns the prefix return prefix# Driver codeif __name__ == '__main__': s = "abcab" ans = longestPrefixSuffix(s) if (ans == ""): print("-1") else: print(ans) # This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approach 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 of computeLPSArray() in KMP Algorithm static int LengthlongestPrefixSuffix(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; // Loop to calculate 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 { // 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; } // Function that returns the prefix static String longestPrefixSuffix(string s) { // Get the length of the longest prefix int len = LengthlongestPrefixSuffix(s); // Stores the prefix string prefix = ""; // Traverse and add characters for (int i = 0; i < len; i++) prefix += s[i]; // Returns the prefix return prefix; } // Driver code public static void Main() { string s = "abcab"; string ans = longestPrefixSuffix(s); if (ans == "") Console.WriteLine("-1"); else Console.WriteLine(ans); }} // This code is contributed by Ryuga |
Javascript
<script>// JavaScript implementation of the approach // Returns length of the longest prefix // which is also suffix and the two do // not overlap. This function mainly is // copy of computeLPSArray() in KMP Algorithm function LengthlongestPrefixSuffix(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; // Loop to calculate 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++; } 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; } // Function that returns the prefix function longestPrefixSuffix(s) { // Get the length of the longest prefix var len = LengthlongestPrefixSuffix(s); // Stores the prefix var prefix = ""; // Traverse and add characters for (var i = 0; i < len; i++) prefix += s.charAt(i); // Returns the prefix return prefix; } // Driver code var s = "abcab"; var ans = longestPrefixSuffix(s); if (ans == "") document.write("-1"); else document.write(ans); // This code contributed by shikhasingrajput </script> |
Output
ab
Time Complexity: O(N), as we are using a loop to traverse N times to build los array. Where N is the length of the string.
Auxiliary Space: O(N), as we are using extra space for the lps array. Where N is the length of the string.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
