970. The Longest Piece Two Strings Share

Two strings s and t are given. Print the length of the longest CONTIGUOUS piece that occurs in both. Print 0 if they share no character at all.

abcdxyz and xyzabcd -> 4 abcd occurs in both abc and xyz -> 0 aaaa and aa -> 2 banana and ananas -> 5 anana mississippi and issipi -> 4 issi

This is a SUBSTRING, so the characters must be adjacent in both strings. abcdefghij and jihgfedcba share only single characters and answer 1.

## The pairwise scan

Start at every position of s and every position of t and extend while the characters agree. That is |s| * |t| starts, each extending up to the shorter length, so O(|s| * |t| * min) and 2.7 * 10^7 character comparisons at the limit of 300 each. It is correct and it repeats enormous amounts of work: the comparison of s from 5 and t from 9 redoes everything the comparison of s from 5 and t from 8 already knew about s.

## One string becomes a structure, the other becomes a query

Insert every suffix of s into a trie, as in problems 953 and 969. That trie contains exactly the pieces of s: every path from the root spells one, and every piece of s is one of those paths.

Now walk t. From each starting position of t, descend the trie as long as the next character has a child, and record how deep you got.

build the suffix trie of s best = 0 for i in 0 .. |t|-1: node = root, depth = 0 for j in i .. |t|-1: if child[node][t[j]] is absent: break node = child[node][t[j]] depth = depth + 1 best = max(best, depth)

## Why the depth reached is the longest shared piece starting there

Descending d levels from the root along t[i], t[i+1], ... means t[i..i+d-1] is a path in the trie, and a path in the trie is a piece of s. The walk stops at the first character that has no child, so t[i..i+d] is NOT a piece of s. So d is exactly the longest piece of s that starts at position i of t, and the maximum over i is the longest piece shared by the two strings, since every shared piece starts somewhere in t.

## Why this is faster than the pairwise scan

Every start in t is walked once against the WHOLE of s at once, rather than once per starting position of s, because the trie has merged all the starting positions of s that agree so far. The comparison work that the pairwise scan repeats is precisely the work the shared trie path does once.

## Boundaries

Two identical strings answer their own length. A string and its own reverse answer 1 unless it contains a repeated block, which is the case worth testing because the pairwise scan and the trie walk can disagree on it if the trie was built from the wrong string. Sharing nothing answers 0, which must be printed rather than treated as no answer.

## The size this costs, computed

The suffix trie of s has at most 1 + |s| (|s| + 1) / 2 nodes, which at |s| = 300 is 45151, and at 26 links of 8 bytes each, 208 bytes a node, that is at most 45151 * 208 = 9391408 bytes, about 9.4 MB. Building the trie from the SHORTER of the two strings is the free optimisation here, since the walk does not care which is which.

## Overflow

Nothing here overflows. The answer is at most 300.

Constraints - `1 ≤ length of s ≤ 300` - `1 ≤ length of t ≤ 300` - Both strings contain only lowercase English letters.