By Lindsey L. (11th Grade)
https://codeforces.com/problemset/problem/126/B 12/26/25
Concepts: hashing, binary search
Since we want to compare two substrings in O(1), we need to do hashing. We can do a polynomial rolling hash, which is
s1bn-1+s2bn-2+ …+sn-1b+sn mod m
for a string of length n. We can choose b to be a small prime like 31, and m to be a large prime like 9982443535 to prevent collisions.
To find the largest matching substrings from the prefix, suffix, and middle, we can first find all possible lengths of matching prefix and suffix substrings, then do a binary search to check if that substring exists in the middle. This will be O(nlog(n)) which is fast enough.
We can first compute hashes for each substring for both the prefix and suffix over all n positions. If the two hashes are equal, it means the substrings are equal and we can add it to our array of possible lengths.
To check if a certain length n works in our binary search, we can calculate the prefix hash again. Then, we can loop through each position in the middle of the string and check if the hashes are equal, each time shifting the range by 1 to the right. To quickly calculate the new hash, we have to subtract the value of the leftmost character s * p^n-1. Then, we can multiply the hash by b and add the new character.
