969. The Longest Piece That Appears Twice

Given a string s, print the length of the longest piece of it that occurs at least TWICE. The two occurrences may overlap. Print 0 if no piece occurs twice, which happens exactly when every character of s is different.

banana -> 3 ana occurs at 1 and at 3, overlapping abcd -> 0 aaaa -> 3 aaa occurs at 0 and at 1 mississippi -> 4 issi occurs at 1 and at 4 abcabc -> 3

Note banana. The two occurrences of ana share the middle a, and the question allows that. Requiring them to be disjoint would make the answer 1.

## The obvious program

For each length from the longest downwards, put every piece of that length in a hash set and stop at the first length where one repeats. That is O(m) pieces per length, each costing its own length to build and hash, so O(m^3) characters in the worst case, about 2.7 * 10^7 at m = 300. It works at this size and it says nothing about why.

## Every piece is a prefix of a suffix

That is problem 953's observation, and it does the work again here. Insert all m suffixes of s into one trie, and this time keep TWO numbers at each node: the depth, and a counter incremented every time an insertion passes through.

Then the counter at a node is the number of suffixes that START with the string that node spells, and a suffix starting with a piece is the same thing as an occurrence of that piece. So

cnt[v] = the number of occurrences of the string v spells

and the answer is the greatest depth among the nodes with cnt at least 2.

for i in 0 .. m-1: node = root for j in i .. m-1: create child[node][s[j]] if absent, with depth = depth[node] + 1 node = child[node][s[j]] cnt[node] += 1 best = max depth over nodes with cnt >= 2, or 0 if there are none

## Why the counter counts occurrences, overlaps included

An occurrence of a piece p at position i is exactly the statement that the suffix starting at i begins with p. Two occurrences at different positions are two different suffixes, whether or not the occurrences overlap in the string, because the suffixes are distinguished by where they start and not by which characters they cover. So counting suffixes through a node counts occurrences, and overlapping comes for free rather than needing to be allowed for.

## Why the deepest such node is the answer

If a piece of length L occurs twice, its node has depth L and counter at least 2. If a node has depth L and counter at least 2, the string it spells is a piece of length L occurring at least twice. The two statements are equivalent, so the maximum depth over qualifying nodes is the maximum length over qualifying pieces.

## The boundary

A string with all different characters has every counter equal to 1 below depth 0, so the maximum is over an empty set and the answer is 0. Starting best at 0 and never assigning it handles this, and the root itself must not be counted: its counter is whatever you make it and its depth is 0, so including it would still print 0, but only by luck.

## The size this costs, computed

The suffix trie has at most 1 + m (m + 1) / 2 nodes, which at m = 300 is 45151. At 26 links of 8 bytes each, 208 bytes a node, that is at most 45151 * 208 = 9391408 bytes, about 9.4 MB. The node count grows with the square of the length, which is why this structure is capped at a few hundred characters and why real tools use a suffix automaton or a suffix array instead.

## Overflow

Nothing here overflows. The largest counter is m, which is 300, and the answer is at most 299.

Constraints - `1 ≤ length of s ≤ 300` - `s` contains only lowercase English letters.