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 = “neveropenisforneveropeninplatformneveropen”
Output: neveropen
Input: str = “fixprefixsuffix”
Output: fix
Note: The Set-1 of this article is attached here.
Approach:
The implementation is using BIT and Z algorithm. Learn more about them from this and this.
- First we are calculating the Z array by using the Z algorithm.
- Update the values in Bit array by 1 from index z[i].
- Querying for the maximum length needed substring using the pref function.
- If len is 0 then such substring is not possible from the given string.
Below is the implementation approach:
C++
// C++ program to find that// substring which is its// suffix prefix and also// found somewhere in between#include <bits/stdc++.h>using namespace std;// Z-algorithm functionvector<int> z_function(string s){ int n = s.size(); vector<int> z(n); for (int i = 1, l = 0, r = 0; i < n; i++) { if (i <= r) z[i] = min(r - i + 1, z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++; if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } return z;}int n, len = 0;// BIT arrayint bit[1000005];string s;vector<int> z;map<int, int> m;// bit update function which// updates values from index// "idx" to last by value "val"void update(int idx, int val){ if (idx == 0) return; while (idx <= n) { bit[idx] += val; idx += (idx & -idx); }}// Query function in bitint pref(int idx){ int ans = 0; while (idx > 0) { ans += bit[idx]; idx -= (idx & -idx); } return ans;}// Driver Codeint main(){ s = "neveropenisforneveropeninplatformneveropen"; n = s.size(); // Making the z array z = z_function(s); // update in the bit array from // index z[i] by increment of 1 for (int i = 1; i < n; i++) { update(z[i], 1); } for (int i = n - 1; i > 1; i--) { // if the value in z[i] is // not equal to (n-i) then no // need to move further if (z[i] != (n - i)) continue; // querying for the maximum // length substring from // bit array if (pref(n) - pref(z[i] - 1) >= 2) { len = max(len, z[i]); } } if (!len) cout << "-1"; else cout << s.substr(0, len); return 0;} |
Java
// Java program to find that// substring which is its// suffix prefix and also// found somewhere in betweenclass GFG{// Z-algorithm functionstatic int[] z_function(char []s){ int n = s.length; int []z = new int[n]; for (int i = 1, l = 0, r = 0; i < n; i++) { if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++; if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; } } return z;}static int n, len = 0;// BIT arraystatic int []bit = new int[1000005];static String s;static int[] z;// bit update function which// updates values from index// "idx" to last by value "val"static void update(int idx, int val){ if (idx == 0) return; while (idx <= n) { bit[idx] += val; idx += (idx & -idx); }}// Query function in bitstatic int pref(int idx){ int ans = 0; while (idx > 0) { ans += bit[idx]; idx -= (idx & -idx); } return ans;}// Driver Codepublic static void main(String[] args){ s = "neveropenisforneveropeninplatformneveropen"; z = new int[s.length()]; n = s.length(); // Making the z array z = z_function(s.toCharArray()); // update in the bit array from // index z[i] by increment of 1 for (int i = 1; i < n; i++) { update(z[i], 1); } for (int i = n - 1; i > 1; i--) { // if the value in z[i] is // not equal to (n-i) then no // need to move further if (z[i] != (n - i)) continue; // querying for the maximum // length substring from // bit array if (pref(n) - pref(z[i] - 1) >= 2) { len = Math.max(len, z[i]); } } if (len == 0) System.out.println("-1"); else System.out.println(s.substring(0, len));}}// This code is contributed // by PrinciRaj1992 |
Python3
# Python3 program to find that# substring which is its# suffix prefix and also# found somewhere in between# Z-algorithm functiondef z_function(s): global z, n n = len(s) z = [0] * n l, r = 0, 0 for i in range(1, n): if i <= r: z[i] = min(r - i + 1, z[i - 1]) while (i + z[i] < n and s[z[i]] == s[i + z[i]]): z[i] += 1 if (i + z[i] - 1 > r): l = i r = i + z[i] - 1 return z# bit update function which# updates values from index# "idx" to last by value "val"def update(idx, val): global bit if idx == 0: return while idx <= n: bit[idx] += val idx += (idx & -idx)# Query function in bitdef pref(idx): global bit ans = 0 while idx > 0: ans += bit[idx] idx -= (idx & -idx) return ans# Driver Codeif __name__ == "__main__": n = 0 length = 0 # BIT array bit = [0] * 1000005 z = [] m = dict() s = "neveropenisforneveropeninplatformneveropen" # Making the z array z = z_function(s) # update in the bit array from # index z[i] by increment of 1 for i in range(1, n): update(z[i], 1) for i in range(n - 1, 1, -1): # if the value in z[i] is # not equal to (n-i) then no # need to move further if z[i] != n - i: continue # querying for the maximum # length substring from # bit array if (pref(n) - pref(z[i] - 1)) >= 2: length = max(length, z[i]) if not length: print(-1) else: print(s[:length])# This code is contributed by# sanjeev2552 |
C#
// C# program to find that// substring which is its// suffix prefix and also// found somewhere in betweenusing System;class GFG{// Z-algorithm functionstatic int[] z_function(char []s){ int n = s.Length; int []z = new int[n]; for (int i = 1, l = 0, r = 0; i < n; i++) { if (i <= r) z[i] = Math.Min(r - i + 1, z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++; if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; } } return z;}static int n, len = 0;// BIT arraystatic int []bit = new int[1000005];static String s;static int[] z;// bit update function which// updates values from index// "idx" to last by value "val"static void update(int idx, int val){ if (idx == 0) return; while (idx <= n) { bit[idx] += val; idx += (idx & -idx); }}// Query function in bitstatic int pref(int idx){ int ans = 0; while (idx > 0) { ans += bit[idx]; idx -= (idx & -idx); } return ans;}// Driver Codepublic static void Main(String[] args){ s = "neveropenisforneveropeninplatformneveropen"; z = new int[s.Length]; n = s.Length; // Making the z array z = z_function(s.ToCharArray()); // update in the bit array from // index z[i] by increment of 1 for (int i = 1; i < n; i++) { update(z[i], 1); } for (int i = n - 1; i > 1; i--) { // if the value in z[i] is // not equal to (n-i) then no // need to move further if (z[i] != (n - i)) continue; // querying for the maximum // length substring from // bit array if (pref(n) - pref(z[i] - 1) >= 2) { len = Math.Max(len, z[i]); } } if (len == 0) Console.WriteLine("-1"); else Console.WriteLine(s.Substring(0, len));}}// This code is contributed by PrinciRaj1992 |
Javascript
// JavaScript program to find that// substring which is its// suffix prefix and also// found somewhere in between// Z-algorithm functionfunction z_function(s) { let n = s.length; let z = Array(n).fill(0); for (let i = 1, l = 0, r = 0; i < n; i++) { if (i <= r) { z[i] = Math.min(r - i + 1, z[i - l]); } while (i + z[i] < n && s[z[i]] === s[i + z[i]]) { z[i]++; } if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; } } return z;}// Driver Codelet n, len = 0;let s = "neveropenisforneveropeninplatformneveropen";n = s.length;let z = z_function(s);let bit = Array(1000005).fill(0);// bit update function which// updates values from index// "idx" to last by value "val"function update(idx, val) { if (idx === 0) return; while (idx <= n) { bit[idx] += val; idx += (idx & -idx); }}// Query function in bitfunction pref(idx) { let ans = 0; while (idx > 0) { ans += bit[idx]; idx -= (idx & -idx); } return ans;}for (let i = 1; i < n; i++) { update(z[i], 1);}for (let i = n - 1; i > 1; i--) { // if the value in z[i] is // not equal to (n-i) then no // need to move further if (z[i] !== n - i) continue; // querying for the maximum // length substring from // bit array if (pref(n) - pref(z[i] - 1) >= 2) { len = Math.max(len, z[i]); }}if (!len) { console.log("-1");} else { console.log(s.substring(0, len));} |
Output:
neveropen
Time complexity: O(N)
Space complexity : O(N)
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!
