P6816 [PA 2009] Quasi-template
Description
Define that a string $s$ can match $S$ if and only if $s$ can cover $S$ while being allowed to extend beyond both the beginning and the end of $S$, and $|s| \le |S|$, and $s$ must be a substring of $S$.
As shown in the figure below.
Given $S$, find the number of distinct strings $s$ and the shortest such $s$. If there are multiple answers, output the lexicographically smallest one.
Input Format
One line containing a string $S$.
Output Format
The first line contains an integer indicating the number of solutions.
The second line contains a string, the shortest $s$. If there are multiple answers, output the lexicographically smallest one.
Explanation/Hint
Valid strings are:
aaaabaabaaab, aaaabaabaaaba, aaabaaba, aaabaabaa, aaabaabaaa, aaabaabaaaba, aabaa, aabaabaa, aabaabaaa, abaabaaa.
Constraints: $|S| \le 2\times 10^5$.
Translated by ChatGPT 5