1814. A Piece at the Start, the End and in Between

Find the longest string that is all three of these at once: a proper prefix of s, a proper suffix of s, and an occurrence somewhere STRICTLY INSIDE s. Strictly inside means it starts at a position of at least 1 and ends at a position of at most n - 2. Print that string, or none.

fixprefixsuffix -> fix at 0, at 12, and once at 3 abcdabc -> none abc is at both ends and nowhere between aaaa -> aa aaa is a border but does not fit strictly inside aabaabaab -> aab aabaab is a border but is too long to fit inside abacaba -> a aba is a border, and only a occurs strictly inside

Read aaaa. The longest border is aaa, covering 0 to 2 and 1 to 3. Neither copy is strictly inside, because one starts at 0 and the other ends at 3. The next border down is aa, which occurs at position 1 covering 1 to 2, and that is strictly inside.

## What most people try first

For each border length from the longest down, scan the string for a middle occurrence. Finding the borders naively is O(n^2) on its own, and each scan is another O(n), so on 200000 identical characters, where every length is a border, it is about 4 * 10^10 character operations. The method below is O(n), about 4 * 10^5.

## Two facts from one table

Build the prefix function once. Then:

inner = max(pi[1], pi[2], ..., pi[n-2]) k = pi[n-1] while k > 0: if k <= inner: print s[0..k-1]; stop k = pi[k-1] print none

inner is the length of the longest prefix of s that ends at a position of at most n-2. The chain from pi[n-1] is every border, longest first, from problem 1805.

## Why comparing against one number is enough

If the prefix of length k ends at some position i <= n-2, then pi[i] >= k, so inner >= k. Conversely, if inner >= k, take the position i <= n-2 where pi[i] = inner. The prefix of length inner ends at i, and every SHORTER prefix of s also ends at i if it is a suffix of that one, which it is, because a prefix of length k <= inner is a prefix of the prefix of length inner, and the prefix of length inner ends at i, so s[i-k+1..i] equals s[inner-k..inner-1]. That is a suffix of the length-inner prefix, not necessarily equal to s[0..k-1].

The correct and simpler statement is this: the prefix of length k occurs ending at position i precisely when k is a border length of s[0..i], and k <= pi[i] is NOT the same as that. What IS true is that the prefix of length k ends somewhere at or before n-2 exactly when k <= inner, because the prefix of length inner ends at some i <= n-2 and its own prefixes of every shorter length end at i - inner + k <= n - 2 as well, being prefixes of a block that starts at i - inner + 1. That start is at least 1, so every shorter prefix also starts at a position of at least 1.

So the test is a single comparison, and the first border on the chain that passes it is the answer.

## Also check the start

A middle occurrence must start at a position of at least 1. pi[i] reports a PROPER border of s[0..i], so its occurrence starts at i - pi[i] + 1 >= 1 always. That is why no separate check on the start is needed.

## Cost

O(n) time and O(n) memory.

Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - the middle occurrence may overlap the prefix copy or the suffix copy