Find the Longest Non-Prefix-Suffix Substring in the Given String - Coding

Given a string s of length n. The task is to determine the longest substring t such that t is neither the prefix nor the suffix of string s, and that substring must appear as both prefix and suffix of the string s. If no such string exists, print -1.

Example:

Input: s = “fixprefixsuffix”
Output: fix

Input: s = “abcdabc”
Output: -1

Approach:

The idea is to use the concept of a prefix function, which is a common technique in string processing algorithms.

Here’s the intuition behind the solution:

Calculate Prefix Function: The prefix function for a string is an array where the i-th element is the length of the longest proper prefix of the substring ending at position i that is also a suffix of this substring. This would be calculated in the calculatePrefixFunction() function. For example, for the string “abcabc”, the prefix function would be [0, 0, 0, 1, 2, 3], indicating that the longest proper prefix which is also a suffix for the substring “abcabc” is “abc” of length 3.

Find Longest Valid Substring: After calculating the prefix function, the next step is to find the longest valid substring that is neither the prefix nor the suffix of the string, but appears as both a prefix and a suffix of the string. This will be handle in our findLongestValidSubstring() function. It iterates over the prefix function array and checks two possible candidates for the longest valid substring: the longest common prefix and suffix for the whole string, and the longest common prefix and suffix for the prefix of the string. These candidates are then compared to find the longest valid substring.

Steps-by-step approach:

Calculate Prefix Function:
- Create a function calculatePrefixFunction() that takes a string s and an array prefixFunction.
- Initialize variables i and j to 0 and -1, respectively.
- Iterate over the characters of the string s.
  - For each character, update the prefixFunction array with the value of j.
- While j is not -1 and the current character is not equal to the character at position j, update j using the value in the prefixFunction array.
- Continue the iteration until you reach the end of the string.
Find Longest Valid Substring:
- Create a function findLongestValidSubstring() that takes a string s and the prefixFunction array.
- Initialize variables longestSubstringLength = 0.
- Iterate over the characters of the string starting from index 1.
  - Check if the current value of the prefixFunction array at position i is equal to the prefixFunction value at the end of the string or the prefixFunction value of the prefixFunction value at the end of the string.
  - If true, update longestSubstringLength with the maximum of its current value and the prefixFunction value at position i.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the prefix function values
void calculatePrefixFunction(const string& s,
                             int prefixFunction[])
{
    int stringSize = s.size();
 
    for (int i = 0, j = -1; i < stringSize;
         prefixFunction[++i] = ++j) {
        while (~j && s[i] != s[j]) {
            j = prefixFunction[j];
        }
    }
}
 
// Function to find the longest valid substring
int findLongestValidSubstring(const string& s,
                              const int prefixFunction[])
{
    int stringSize = s.size();
    int longestSubstringLength = 0;
 
    for (int i = 1; i < stringSize; i++) {
        if (prefixFunction[i] == prefixFunction[stringSize]
            || prefixFunction[i]
                   == prefixFunction
                       [prefixFunction[stringSize]]) {
            longestSubstringLength = max(
                longestSubstringLength, prefixFunction[i]);
        }
    }
 
    return longestSubstringLength;
}
 
int main()
{
    // Input string
    string s = "fixprefixsuffix";
 
    // Size of the input string
    int stringSize = s.size();
 
    // Array to store prefix function values
    int prefixFunction[stringSize + 1] = { -1 };
 
    // Calculate prefix function values
    calculatePrefixFunction(s, prefixFunction);
 
    // Find the longest valid substring
    int longestSubstringLength
        = findLongestValidSubstring(s, prefixFunction);
 
    // Output the longest valid substring if it exists,
    // otherwise output "-1"
    cout << (longestSubstringLength
                 ? s.substr(0, longestSubstringLength)
                 : "-1");
}

Java

public class LongestValidSubstring {
 
    // Function to calculate the prefix function values
    public static int[] calculatePrefixFunction(String s) {
        int stringSize = s.length();
        int[] prefixFunction = new int[stringSize + 1];
        prefixFunction[0] = -1;
 
        int j = -1;
        for (int i = 0; i < stringSize; ) {
            while (j >= 0 && s.charAt(i) != s.charAt(j)) {
                j = prefixFunction[j];
            }
            prefixFunction[++i] = ++j;
        }
 
        return prefixFunction;
    }
 
    // Function to find the longest valid substring
    public static int findLongestValidSubstring(String s, int[] prefixFunction) {
        int stringSize = s.length();
        int longestSubstringLength = 0;
 
        for (int i = 1; i < stringSize; i++) {
            if (prefixFunction[i] == prefixFunction[stringSize] ||
                prefixFunction[i] == prefixFunction[prefixFunction[stringSize]]) {
                longestSubstringLength = Math.max(longestSubstringLength, prefixFunction[i]);
            }
        }
 
        return longestSubstringLength;
    }
 
    public static void main(String[] args) {
        // Input string
        String s = "fixprefixsuffix";
 
        // Calculate prefix function values
        int[] prefixFunction = calculatePrefixFunction(s);
 
        // Find the longest valid substring
        int longestSubstringLength = findLongestValidSubstring(s, prefixFunction);
 
        // Output the longest valid substring if it exists,
        // otherwise output "-1"
        System.out.println(longestSubstringLength != 0 ? s.substring(0, longestSubstringLength) : "-1");
    }
}
 
// This code is contributed by shivamgupta0987654321

Python3

def calculate_prefix_function(s):
    string_size = len(s)
    prefix_function = [-1] * (string_size + 1)
     
    j = -1
    for i in range(string_size):
        while j >= 0 and s[i] != s[j]:
            j = prefix_function[j]
        j += 1
        prefix_function[i + 1] = j
     
    return prefix_function
 
def find_longest_valid_substring(s, prefix_function):
    string_size = len(s)
    longest_substring_length = 0
     
    for i in range(1, string_size):
        if prefix_function[i] == prefix_function[string_size] or prefix_function[i] == prefix_function[prefix_function[string_size]]:
            longest_substring_length = max(longest_substring_length, prefix_function[i])
     
    return longest_substring_length
 
if __name__ == "__main__":
    # Input string
    s = "fixprefixsuffix"
     
    # Calculate prefix function values
    prefix_function = calculate_prefix_function(s)
     
    # Find the longest valid substring
    longest_substring_length = find_longest_valid_substring(s, prefix_function)
     
    # Output the longest valid substring if it exists, otherwise output "-1"
    if longest_substring_length:
        print(s[:longest_substring_length])
    else:
        print("-1")
 
# This code is contributed by shivamgupta0987654321

C#

//C# code
using System;
 
public class GFG
{
    // Function to calculate the prefix function values
    public static int[] CalculatePrefixFunction(string s)
    {
        int stringSize = s.Length;
        int[] prefixFunction = new int[stringSize + 1];
        prefixFunction[0] = -1;
 
        int j = -1;
        for (int i = 0; i < stringSize;)
        {
            while (j >= 0 && s[i] != s[j])
            {
                j = prefixFunction[j];
            }
            prefixFunction[++i] = ++j;
        }
 
        return prefixFunction;
    }
 
    // Function to find the longest valid substring
    public static int FindLongestValidSubstring(string s, int[] prefixFunction)
    {
        int stringSize = s.Length;
        int longestSubstringLength = 0;
 
        for (int i = 1; i < stringSize; i++)
        {
            if (prefixFunction[i] == prefixFunction[stringSize] ||
                prefixFunction[i] == prefixFunction[prefixFunction[stringSize]])
            {
                longestSubstringLength = Math.Max(longestSubstringLength, prefixFunction[i]);
            }
        }
 
        return longestSubstringLength;
    }
 
    public static void Main(string[] args)
    {
        // Input string
        string s = "fixprefixsuffix";
 
        // Calculate prefix function values
        int[] prefixFunction = CalculatePrefixFunction(s);
 
        // Find the longest valid substring
        int longestSubstringLength = FindLongestValidSubstring(s, prefixFunction);
 
        // Output the longest valid substring if it exists,
        // otherwise output "-1"
        Console.WriteLine(longestSubstringLength != 0 ? s.Substring(0, longestSubstringLength) : "-1");
    }
}

Javascript

// Function to calculate the prefix function values
function calculatePrefixFunction(s) {
    let stringSize = s.length;
    let prefixFunction = new Array(stringSize + 1).fill(-1);
 
    for (let i = 0, j = -1; i < stringSize; prefixFunction[++i] = ++j) {
        while (j >= 0 && s.charAt(i) !== s.charAt(j)) {
            j = prefixFunction[j];
        }
    }
 
    return prefixFunction;
}
 
// Function to find the longest valid substring
function findLongestValidSubstring(s, prefixFunction) {
    let stringSize = s.length;
    let longestSubstringLength = 0;
 
    for (let i = 1; i < stringSize; i++) {
        if (
            prefixFunction[i] === prefixFunction[stringSize] ||
            prefixFunction[i] === prefixFunction[prefixFunction[stringSize]]
        ) {
            longestSubstringLength = Math.max(
                longestSubstringLength,
                prefixFunction[i]
            );
        }
    }
 
    return longestSubstringLength;
}
 
// Input string
let s = "fixprefixsuffix";
 
// Calculate prefix function values
let prefixFunction = calculatePrefixFunction(s);
 
// Find the longest valid substring
let longestSubstringLength = findLongestValidSubstring(s, prefixFunction);
 
// Output the longest valid substring if it exists,
// otherwise output "-1"
console.log(
    longestSubstringLength
        ? s.substring(0, longestSubstringLength)
        : "-1"
);

Output

fix

Time Complexity: O(N)
Auxiliary Space: O(N)

Reffered: https://www.geeksforgeeks.org

Competitive Programming

Related
Minimizing and Maximizing longest Increasing Subsequence (LIS)
Sum and Update Queries on 3D Matrix in log(N) time
Connecting Nodes in a Graph with Sum-based Edge Conditions
Heap Data Structure for Competitive Programming
Competitive Programming (CP) Handbook with Complete Roadmap

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	16