1817. Where the Text Agrees Longest With the Word

Given a text a and a word b, look at every starting position i in a and ask how many characters of a from i onwards agree with b from its start. Print the largest such length, and the SMALLEST i that achieves it.

xxabcyy, abcd -> 3 2 aaaa, aa -> 2 0 positions 0, 1 and 2 all agree fully banana, ana -> 3 1 positions 1 and 3 both agree fully abcdef, f -> 1 5 abc, xyz -> 0 0 nothing agrees, so the index is 0

The agreement stops for one of three reasons: the characters differ, a runs out, or b runs out. In abcab against abcabc the agreement from 0 is 5, because a runs out first.

When no position agrees on even one character, print 0 0.

## What most people try first

From each i, walk forward comparing. That is O(|a| * |b|): at 200000 and 200000 identical characters, about 4 * 10^10 comparisons. The method below is about 8 * 10^5.

## One Z array over the pair

g = b + '#' + a agree(i) = min(z[|b| + 1 + i], |b|)

z[j] is how far position j of g agrees with the beginning of g, and the beginning of g is b. The separator already caps every value after it at |b|, so the explicit min is belt and braces rather than a correction.

Sweep i upwards and keep the best, replacing only on a STRICTLY larger value. That is what makes the reported index the smallest one.

## Why the strict comparison matters

On aaaa against aa, the agreement is 2 at positions 0, 1 and 2. Replacing the best on >= rather than > reports position 2. Both are "a longest agreement", and the problem pins the tie so that there is exactly one correct output.

## Cost

O(|a| + |b|) time and memory.

Constraints - `1 ≤ length of a ≤ 200000` - `1 ≤ length of b ≤ 200000` - both strings contain only lowercase English letters - the answer is capped by the length of `b` and by how much of `a` is left - agreements starting at different positions may overlap each other freely, and one length with one position is wanted