676. How Much Two Words Share at Their Ends
Two words are given. Print two numbers: the length of their longest common PREFIX, and then the length of their longest common SUFFIX taken from what is left after removing that prefix.
The two pieces never overlap, so together they never exceed either word's length.
abcde and abxde -> 2 2 prefix ab, suffix de
abc and abc -> 3 0 the prefix takes everything
ab and b -> 0 1
## Two sweeps, one from each end
``` p = 0 while p < n and p < m and x[p] == y[p]: p += 1
i = n-1, j = m-1, s = 0 while i >= p and j >= p and x[i] == y[j]: s += 1; i -= 1; j -= 1 ```
The prefix sweep walks a single cursor forward through both words at once, because the prefix occupies the same positions in each. The suffix sweep needs TWO cursors, because the words may differ in length and the suffix sits at different positions.
## The bound that prevents overlap
Both suffix cursors stop at p, not at 0. Without that, abc against abc would report a
prefix of 3 AND a suffix of 3, counting the same characters twice and reporting more than the
word contains.
With the bound it reports 3 0, which is what the statement asks for: the suffix is measured
in what remains.
Choosing where a second sweep must stop, so the two do not double count, is the real content here. It is the same care that 654's inner loops need.
## Why the prefix is taken first
The order is a choice and the statement fixes it: prefix first, then suffix from the remainder.
The other order gives different numbers on aaa against aa, so the problem would be
ambiguous without saying which.
As written, aaa against aa gives 2 0.
## Boundaries
Words sharing nothing give 0 0. Identical words give their length and 0.
## Cost
Time O(n + m). Space O(1).
Constraints - `1 ≤ length of each word ≤ 200000` - both words contain only lowercase letters
Input
The first line contains the first word. The second line contains the second word.
Output
Print two integers on one line separated by a space: the common prefix length, then the common suffix length measured in what remains.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.