Longest Non-Overlapping Prefix Suffix

Find the longest prefix of a string that is also a suffix, ensuring they do not overlap.

Understand the Problem

Problem Statement

Longest Non-Overlapping Prefix Suffix: The program must accept a string S as the input. Then the program must print the longest prefix in the string S which is also a suffix. The prefix and the suffix must not overlap. If there is no such prefix, then the program must print -1 as the output.

Constraints

1 <= Length of S <= 10^8
String S consists of only lowercase and uppercase alphabets.
Prefix and suffix must not overlap.

Examples

Example 1

Input

abcefgabc

Output

abc

Explanation

The string 'abc' is a prefix of 'abcefgabc' and also a suffix ('abcefgabc'). The length of 'abc' is 3, which is less than half the string length (9/2 = 4.5), so it doesn't overlap.

Example 2

Input

skillrack

Output

-1

Explanation

There is no prefix of 'skillrack' that is also a suffix.

Example 3

Input

tutortutor

Output

tutor

Explanation

The string 'tutor' is a prefix of 'tutortutor' and also a suffix ('tutortutor'). The length of 'tutor' is 5, which is less than half the string length (10/2 = 5), so it doesn't overlap.

Solution

#include <stdio.h>
#include <string.h>

int lengthLPS(char *s, int n) {
    int lps[n];
    int len = 0;
    int i = 1;
    lps[0] = 0;

    while (i < n) {
        if (s[i] == s[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps[n - 1];
}

int main() {
    char s[100000001];
    fgets(s, sizeof(s), stdin);
    int n = strlen(s);
    if (s[n - 1] == '\n') {
        s[n - 1] = '\0';
        n--;
    }

    int res = lengthLPS(s, n);
    if (res > n / 2) {
        res = lengthLPS(s, res);
    }

    if (res == 0) {
        printf("-1\n");
    } else {
        for (int i = 0; i < res; i++) {
            printf("%c", s[i]);
        }
        printf("\n");
    }
    return 0;
}

Time:O(n)

Space:O(n)

Approach:

The C solution implements the KMP LPS algorithm to find the longest prefix which is also a suffix without overlap.

1. lengthLPS function: This function builds the LPS array for the input string. It iterates through the string, comparing characters to find the longest proper prefix which is also a suffix for every substring ending at position i.

2. Overlap Check: After getting the LPS value for the last character, it checks if this length is greater than half the string length. If it is, it means the prefix and suffix would overlap. In this case, it recursively finds the LPS value for the prefix of that length.

3. Output: If the final length is 0, it prints -1. Otherwise, it prints the prefix of that length.

4. Input Handling: The program uses fgets to read the input string and handles the newline character that fgets includes.

Visual Explanation

Loading diagram...

All Problems