前置知识
前缀 是指从串首开始到某个位置 \(i\) 结束的一个特殊子串.
真前缀 指除了 \(S\) 本身的 \(S\) 的前缀.
举例来说, 字符串 abcabeda 的所有前缀为 {a, ab, abc, abca, abcab, abcabe, abcabed, abcabeda}, 而它的真前缀为 {a, ab, abc, abca, abcab, abcabe, abcabed}.
后缀 是指从某个位置 \(i\) 开始到整个串末尾结束的一个特殊子串.
真后缀 指除了 \(S\) 本身的 \(S\) 的后缀.
举例来说, 字符串 abcabeda 的所有后缀为 {a, da, eda, beda, abeda, cabeda, bcabeda, abcabeda}, 而它的真后缀为 {a, da, eda, beda, abeda, cabeda, bcabeda}.
前缀函数
定义: 给定一个长度为 \(n\) 的字符串 \(s\), 其前缀函数被定义为一个长度为 \(n\) 的数组 nxt. 其中 nxt[i] 是子串 s[0 ~ i] 最长的相等的真前缀和真后缀的长度.
用数学语言描述如下:
\[nxt \left [i \right ] = \max_{k = 0 \sim i} \{s \left[0 \sim k - 1 \right ] = s \left[i - \left(k - 1 \right) \sim i \right]\}\]
07-11 03:44