1 约定 字符的非空有限集，称为字母表 (alphabet)。 字母表中字符的有限序列，称为字符串 (string)。 字符串中字符的个数，称为该字符串的长度 (length)。 字符串中连续的一段，称为该字符串的子串 (substring)。 字符串中反转后与反转前相同的子串，称为该字符串的回文子串 (palindromic substring)。 字符串中长度最大的回文子串，称为该字...

后缀自动机 回顾 我们来复习一下 DFA （确定有限状态自动机）的定义： 字符集 $\Sigma $ ，自动机只能输入这些字符，对于小写英文字符串，Σ=abcd...z\Sigma = \texttt{abcd...z}Σ=abcd...z，对于 01 字符串，Σ=01\Sigma = \texttt{01}Σ=01 。 状态集合 QQQ ，如果我们把 DFA 看成一张图，QQ...

我们有两个字符串： A=“abbaabbbabaa” B=“abbaaba” 显然第一个位置不能匹配： 12abbaabb(x)babaaabbaaba(x) 我们要不要暴力移动？ 12abbaabbbabaa abbaaba 显然不是最优的！ 考虑我们1~7位已经匹配了，说明A[1→7]=B[1→7]A[1 \to 7] = B[1 \to 7]A[1→7]=B[1→7] 我们需要找到一个...