Longest Happy Prefix

hard strings kmp prefix function

Problem

A happy prefix is a non-empty prefix of a string that is also a suffix (but not the whole string itself). Given a string s of lowercase letters, return the longest happy prefix of s, or "" if none exists.

Inputs = "level"

Output"l"

The proper prefixes are "l", "le", "lev", "leve"; the only one that is also a suffix is "l".

Inputs = "ababab"

Output"abab"

"abab" is both a prefix and a suffix; the prefix and suffix may overlap.

s (lowercase letters)

def longest_prefix(s):
    n = len(s)
    lps = [0] * n          # lps[i] = longest prefix==suffix of s[:i+1]
    length = 0             # length of current matching prefix
    i = 1
    while i < n:
        if s[i] == s[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length > 0:
            length = lps[length - 1]   # fall back
        else:
            lps[i] = 0
            i += 1
    return s[:lps[n - 1]]   # answer is a prefix of that length

function longestPrefix(s) {
  const n = s.length;
  const lps = new Array(n).fill(0); // lps[i] = longest prefix==suffix
  let length = 0;                   // length of current matching prefix
  let i = 1;
  while (i < n) {
    if (s[i] === s[length]) {
      length++;
      lps[i] = length;
      i++;
    } else if (length > 0) {
      length = lps[length - 1];     // fall back
    } else {
      lps[i] = 0;
      i++;
    }
  }
  return s.slice(0, lps[n - 1]);    // answer is a prefix of that length
}

String longestPrefix(String s) {
    int n = s.length();
    int[] lps = new int[n];         // lps[i] = longest prefix==suffix
    int length = 0;                 // length of current matching prefix
    int i = 1;
    while (i < n) {
        if (s.charAt(i) == s.charAt(length)) {
            length++;
            lps[i] = length;
            i++;
        } else if (length > 0) {
            length = lps[length - 1];   // fall back
        } else {
            lps[i] = 0;
            i++;
        }
    }
    return s.substring(0, lps[n - 1]);  // prefix of that length
}

string longestPrefix(string s) {
    int n = s.size();
    vector<int> lps(n, 0);          // lps[i] = longest prefix==suffix
    int length = 0;                 // length of current matching prefix
    int i = 1;
    while (i < n) {
        if (s[i] == s[length]) {
            length++;
            lps[i] = length;
            i++;
        } else if (length > 0) {
            length = lps[length - 1];   // fall back
        } else {
            lps[i] = 0;
            i++;
        }
    }
    return s.substr(0, lps[n - 1]);     // prefix of that length
}

Explanation

A happy prefix is exactly a border of the string: a prefix that is also a suffix. The longest such border is precisely what the KMP prefix function (the lps array) computes, so this hard problem reduces to one well-known linear scan.

We define lps[i] as the length of the longest proper prefix of s[0..i] that is also a suffix of s[0..i]. We build it left to right with two indices: i scans the string, and length is the length of the prefix we are currently trying to extend.

When s[i] == s[length] the current border grows by one: we set lps[i] = ++length and advance i. On a mismatch with length > 0 we do not reset to zero; instead we fall back to length = lps[length - 1], the next-shorter border that might still extend. Only when length is already 0 do we record lps[i] = 0 and move on.

The fall-back is what makes the scan linear: i never moves backward, and each fall-back strictly decreases length, so the total work is O(n).

After the scan, lps[n - 1] is the length of the longest prefix that is also a suffix of the whole string. The answer is just that prefix, s[:lps[n - 1]]. For "ababab" the final value is 4, giving "abab".

Time: O(n) Space: O(n)