1831. The Longest Palindrome, at Full Size
Print the length of the longest contiguous piece of s that reads the same
forwards and backwards, and the SMALLEST position at which such a piece begins.
babad -> 3 0 bab at 0, and aba at 1 is the same length
cbbd -> 2 1 bb, an EVEN palindrome
aaaa -> 4 0
forgeeksskeegfor -> 10 3
abcda -> 1 0
Problem 509 asks for the same LENGTH at |s| <= 5000, where expanding around
each of the 2n - 1 centres costs O(n^2), about 2.5 * 10^7 comparisons, and
is the intended answer. Here |s| reaches 200000, the same method costs about
4 * 10^10, and a starting position is wanted as well.
## What most people try first
Expand around every centre. There are 2n - 1 centres, n characters and
n - 1 gaps between adjacent characters, and each expansion can run to the ends
of the string. On 200000 identical characters every expansion runs in full,
giving about 10^10 comparisons. The method below does about 4 * 10^5.
## Manacher: remember the palindrome that reaches furthest right
Keep two arrays. d1[i] is the number of ODD palindromes centred at i, so the
longest one centred there has length 2 d1[i] - 1. d2[i] is the number of
EVEN palindromes whose right half starts at i, so the longest one has length
2 d2[i].
for the odd pass, keep the interval [l, r] of the rightmost palindrome found:
k = 1 if i > r else min(d1[l + r - i], r - i + 1)
while the characters at i-k and i+k agree: k = k + 1
d1[i] = k
if i + k - 1 > r: l = i - k + 1; r = i + k - 1
The even pass is the same with the centre sitting between two characters.
## Why it is linear
Inside the known interval, position i mirrors position l + r - i, so the
mirrored radius is a free starting guess. It must be capped at r - i + 1,
because beyond r nothing has been compared. Every character comparison that
the while loop actually performs either fails, ending that centre, or pushes
r further right. r moves right at most n times in total, so the loops do
O(n) work across the whole run.
## Finding the smallest start
The arrays give the best LENGTH directly. To get the smallest start, sweep i
upwards and stop at the first i where s[i .. i+best-1] is a palindrome, which
is a constant-time test:
isPalindrome(l, r):
L = r - l + 1
if L is odd: d1[(l + r) / 2] >= (L + 1) / 2
else: d2[(l + r + 1) / 2] >= L / 2
On babad both bab and aba have length 3, and the sweep reports 0.
## Handling both parities
An implementation with only odd centres answers 1 on cbbd instead of 2, and
one with only even centres answers 0 on babad. Both return a plausible number,
which is what makes the omission hard to notice.
## Cost
O(n) time and O(n) memory.
Constraints - `1 ≤ length of s ≤ 200000` - `s` contains only lowercase English letters - a single character is a palindrome, so the length is always at least 1 - palindromic pieces at different positions may overlap each other, and one length with one position is wanted
Input
A single line containing the string s, of lowercase English letters.
Output
Print two integers separated by one space on one line: the length of the longest contiguous palindromic piece of s, and the smallest 0-based position at which a piece of that length begins.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.