思路
动态规划,时间复杂度 $O(nlogn)$。
用 $f(i)$ 表示 $s[0, i]$ 能否作为词根,等价于 $s[i + 1, n - 1]$ 是否由若干后缀构成。
若 $s[i + 1, n - 1]$ 是若干后缀,则可从 $s[i + 1]$ 开始拆出一个后缀,以长度为 $2$ 举例。若 $s[i + 1, i + 2]$ 是一个后缀,则 $s[i + 3, n - 1]$ 必须是若干后缀,等价于 $f(i + 2) = true$。此外,以下条件必须满足其一:
- 若 $s[i + 1, i + 2] = s[i + 3, i + 4]$,则下一个后缀的长度必须是 $3$,即 $s[i + 3, i + 5]$ 必须是一个后缀,则 $s[i + 6, n - 1]$ 是若干个后缀,等价于 $f(i + 5) = true$。
- 若 $s[i + 1, i + 2] \ne s[i + 3, i + 4]$,则已经满足要求。
长度为 $3$ 的情况同理。
由于整个串可以作为词根,因此 $f(n - 1) = true$。
N = 10010
f = [False] * N
ans = set()
s = input()
n = len(s)
f[n - 1] = True
for i in range(n - 3, 3, -1):
for l in (2, 3):
if f[i + l]:
s1, s2 = s[i + 1:i + 1 + l], s[i + 1 + l:i + 1 + l + l]
f[i] = s1 != s2 or f[i + 5]
if f[i]: ans.add(s1)
print(len(ans))
for s in sorted(ans): print(s)
好!