I understand the “hint” part and the procedure of solution 1.
However, solution 1 simply checks whether the gap between any of two matches of a candidate template is less than the length of the template. If two occurrences of the template overlap, why the suffix and prefix are identical?
Thank you for your explanation, I feel rather stupid now.
I’ve complicated the problem too much… I tried to prove by finding another string which is identical to both the prefix and the suffix, but I failed. In fact they’re both equal to the text string, apparently.