Given string str. The task is to find the longest sub-string which is a prefix, a suffix, and a sub-string of the given string, str. If no such string exists then print -1.
Examples:
Input: str = “fixprefixsuffix”
Output: fix
“fix” is a prefix, suffix and present inside in the string too.
Input: str = “aaaa”
“aa” is a prefix, suffix and present inside the string.
Approach: Let us calculate the longest prefix suffix for all prefixes of string. longest prefix suffix lps[i] is maximal length of prefix that also is suffix of substring [0…i]. More about the longest prefix suffix you can see in a description of kmp algorithm.
The first possible answer is a prefix of length lps[n-1]. If lps[n-1] = 0, there is no solution. For checking the first possible answer you should iterate over lps[i]. If at least one of them equal to lps[n-1] (but not n-1th, of course) – you found the answer. The second possible answer is a prefix of length lps[lps[n-1]-1]. If lps[lps[n-1]-1] = 0, you also have no solution. Otherwise, you can be sure that the answer already found. This substring is a prefix and a suffix of our string. Also, it is a suffix of a prefix with length lps[n-1] that places inside of all strings. This solution works in O(n).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to find longest prefix suffixvector<int> compute_lps(string s){ int n = s.size(); // To store longest prefix suffix vector<int> lps(n); // Length of the previous // longest prefix suffix int len = 0; // lps[0] is always 0 lps[0] = 0; int i = 1; // Loop calculates lps[i] for i = 1 to n - 1 while (i < n) { if (s[i] == s[len]) { len++; lps[i] = len; i++; } // (pat[i] != pat[len]) else { if (len != 0) len = lps[len - 1]; // Also, note that we do not increment // i here // If len = 0 else { lps[i] = 0; i++; } } } return lps;}// Function to find the longest substring// which is prefix as well as a// sub-string of s[1...n-2]void Longestsubstring(string s){ // Find longest prefix suffix vector<int> lps = compute_lps(s); int n = s.size(); // If lps of n-1 is zero if (lps[n - 1] == 0) { cout << -1; return; } for (int i = 0; i < n - 1; i++) { // At any position lps[i] equals to lps[n - 1] if (lps[i] == lps[n - 1]) { cout << s.substr(0, lps[i]); return; } } // If answer is not possible if (lps[lps[n - 1] - 1] == 0) cout << -1; else cout << s.substr(0, lps[lps[n - 1] - 1]);}// Driver codeint main(){ string s = "fixprefixsuffix"; // function call Longestsubstring(s); return 0;} |
Java
// Java implementation of the approachclass GFG{ // Function to find longest prefix suffix static int [] compute_lps(String s) { int n = s.length(); // To store longest prefix suffix int [] lps = new int [n]; // Length of the previous // longest prefix suffix int len = 0; // lps[0] is always 0 lps[0] = 0; int i = 1; // Loop calculates lps[i] for i = 1 to n - 1 while (i < n) { if (s.charAt(i) == s.charAt(len)) { len++; lps[i] = len; i++; } // (pat[i] != pat[len]) else { if (len != 0) len = lps[len - 1]; // Also, note that we do not increment // i here // If len = 0 else { lps[i] = 0; i++; } } } return lps; } // Function to find the longest substring // which is prefix as well as a // sub-string of s[1...n-2] static void Longestsubstring(String s) { // Find longest prefix suffix int [] lps = compute_lps(s); int n = s.length(); // If lps of n-1 is zero if (lps[n - 1] == 0) { System.out.println(-1); return; } for (int i = 0; i < n - 1; i++) { // At any position lps[i] equals to lps[n - 1] if (lps[i] == lps[n - 1]) { System.out.println(s.substring(0, lps[i])); return; } } // If answer is not possible if (lps[lps[n - 1] - 1] == 0) System.out.println(-1); else System.out.println(s.substring(0, lps[lps[n - 1] - 1])); } // Driver code public static void main (String [] args) { String s = "fixprefixsuffix"; // function call Longestsubstring(s); }}// This code is contributed by ihritik |
Python3
# Python3 implementation of the approach# Function to find longest prefix suffixdef compute_lps(s): n = len(s) # To store longest prefix suffix lps = [0 for i in range(n)] # Length of the previous # longest prefix suffix Len = 0 # lps[0] is always 0 lps[0] = 0 i = 1 # Loop calculates lps[i] for i = 1 to n - 1 while (i < n): if (s[i] == s[Len]): Len += 1 lps[i] = Len i += 1 # (pat[i] != pat[Len]) else: if (Len != 0): Len = lps[Len - 1] # Also, note that we do not increment # i here # If Len = 0 else: lps[i] = 0 i += 1 return lps# Function to find the longest substring# which is prefix as well as a# sub-of s[1...n-2]def Longestsubstring(s): # Find longest prefix suffix lps = compute_lps(s) n = len(s) # If lps of n-1 is zero if (lps[n - 1] == 0): print(-1) exit() for i in range(0,n - 1): # At any position lps[i] equals to lps[n - 1] if (lps[i] == lps[n - 1]): print(s[0:lps[i]]) exit() # If answer is not possible if (lps[lps[n - 1] - 1] == 0): print(-1) else: print(s[0:lps[lps[n - 1] - 1]])# Driver codes = "fixprefixsuffix"# function callLongestsubstring(s)# This code is contributed by mohit kumar |
C#
// C# implementation of the approachusing System;class GFG{ // Function to find longest prefix suffix static int [] compute_lps(string s) { int n = s.Length; // To store longest prefix suffix int [] lps = new int [n]; // Length of the previous // longest prefix suffix int len = 0; // lps[0] is always 0 lps[0] = 0; int i = 1; // Loop calculates lps[i] for i = 1 to n - 1 while (i < n) { if (s[i] == s[len]) { len++; lps[i] = len; i++; } // (pat[i] != pat[len]) else { if (len != 0) len = lps[len - 1]; // Also, note that we do not increment // i here // If len = 0 else { lps[i] = 0; i++; } } } return lps; } // Function to find the longest substring // which is prefix as well as a // sub-string of s[1...n-2] static void Longestsubstring(string s) { // Find longest prefix suffix int [] lps = compute_lps(s); int n = s.Length; // If lps of n-1 is zero if (lps[n - 1] == 0) { Console.WriteLine(-1); return; } for (int i = 0; i < n - 1; i++) { // At any position lps[i] equals to lps[n - 1] if (lps[i] == lps[n - 1]) { Console.WriteLine(s.Substring(0, lps[i])); return; } } // If answer is not possible if (lps[lps[n - 1] - 1] == 0) Console.WriteLine(-1); else Console.WriteLine(s.Substring(0, lps[lps[n - 1] - 1])); } // Driver code public static void Main () { string s = "fixprefixsuffix"; // function call Longestsubstring(s); }}// This code is contributed by ihritik |
PHP
<?php// Python3 implementation of the approach // Function to find longest prefix suffix function compute_lps($s) { $n = strlen($s); // To store longest prefix suffix $lps = array(); // Length of the previous // longest prefix suffix $len = 0; // lps[0] is always 0 $lps[0] = 0; $i = 1; // Loop calculates lps[i] for i = 1 to n - 1 while ($i < $n) { if ($s[$i] == $s[$len]) { $len++; $lps[$i] = $len; $i++; } // (pat[i] != pat[len]) else { if ($len != 0) $len = $lps[$len - 1]; // Also, note that we do not increment // i here // If len = 0 else { $lps[$i] = 0; $i++; } } } return $lps; } // Function to find the longest substring // which is prefix as well as a // sub-string of s[1...n-2] function Longestsubstring($s) { // Find longest prefix suffix $lps = compute_lps($s); $n = strlen($s); // If lps of n-1 is zero if ($lps[$n - 1] == 0) { echo -1; return; } for ($i = 0; $i < $n - 1; $i++) { // At any position lps[i] equals to lps[n - 1] if ($lps[$i] == $lps[$n - 1]) { echo substr($s, 0, $lps[$i]); return; } } // If answer is not possible if ($lps[$lps[$n - 1] - 1] == 0) echo -1; else echo substr($s, 0, $lps[$lps[$n - 1] - 1]); } // Driver code $s = "fixprefixsuffix"; // function call Longestsubstring($s); // This code is contributed by Ryuga?> |
Javascript
<script>// Javascript implementation of the approach// Function to find longest prefix suffixfunction compute_lps(s){ var n = s.length; // To store longest prefix suffix var lps = Array(n); // Length of the previous // longest prefix suffix var len = 0; // lps[0] is always 0 lps[0] = 0; var i = 1; // Loop calculates lps[i] for i = 1 to n - 1 while (i < n) { if (s[i] == s[len]) { len++; lps[i] = len; i++; } // (pat[i] != pat[len]) else { if (len != 0) len = lps[len - 1]; // Also, note that we do not increment // i here // If len = 0 else { lps[i] = 0; i++; } } } return lps;}// Function to find the longest substring// which is prefix as well as a// sub-string of s[1...n-2]function Longestsubstring( s){ // Find longest prefix suffix var lps = compute_lps(s); var n = s.length; // If lps of n-1 is zero if (lps[n - 1] == 0) { document.write( -1); return; } for (var i = 0; i < n - 1; i++) { // At any position lps[i] equals to lps[n - 1] if (lps[i] == lps[n - 1]) { document.write( s.substring(0, lps[i])); return; } } // If answer is not possible if (lps[lps[n - 1] - 1] == 0) document.write( -1); else document.write( s.substr(0, lps[lps[n - 1] - 1]));}// Driver codevar s = "fixprefixsuffix";// function callLongestsubstring(s);</script> |
Output:
fix
Time Complexity : O(N)
Auxiliary Space: O(N), since N extra space has been taken.
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!
