后缀自动机
「CTSC2012」熟悉的文章-广义后缀自动机
· ✏️ 1139 words · ☕ 3 mins read

为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”,小强想出了一个评定作文 “熟悉程度”的量化指标:$L_0$ .小强首先将作文转化成一个 $01$ 串。之后,小强搜集了各路名家的文章,同样分别转化成 $01$ 串后,整理出一个包含了 $M$ 个 $01$ 串的“ 标准作文库 ”。

小强认为:如果一个 $01$ 串长度不少于 $L$ 且在 标准作文库 中的某个串里出现过(即,它是 标准作文库 的 某个串 的一个 连续子串 ),那么它是“ 熟悉 ”的。对于一篇作文(一个 $01$ 串)A,如果能够把 A 分割成若干段子串,其中“ 熟悉 ” 的子串的 长度总和 不少于 A 总长度的 $90%$,那么称 A 是 “ 熟悉的文章 ”。 $L_0$ 是能够让 $A$ 成为 “ 熟悉的文章 ” 的 所有 $L$ 的最大值 (如果不存在这样的 $L$ ,那么规定 $L_0 = 0$ )。