Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

查缺补漏 冲刺icpc

前缀函数

前缀函数 \pi[i] 代表在字符串 s 中, 以 i 结尾的字串中, 最长的相等的前后缀, 即前 \pi[i] 个字符组成的字符串和后 \pi[i] 个字符组成的字符串是相等的.

对于字符串的第 i 个字符, 当前 i-1 个前缀函数都已求出时, 考虑求出 \pi[i].

\pi[i] 的值是前多少个字符和后多少个字符相等, 如果第 \pi[i-1] + 1 个字符与新加入的第 i 个字符相等, 即之前字符串的前缀等于后缀, 如果新加入的这个字符等于之前相等前缀的后一个字符, 那么这个位置的前缀函数就是之前字符串前缀函数值加一.

如果不相等, 考虑前缀函数的前缀与后缀相等, 前缀一定是从1开始, 后缀一定在 i-1 结束. 并且显然, 此时新加入的位置的前缀函数不会比之前字符串最后的前缀函数值大, 因为第 \pi[i-1] + 1 个字符与新加入的第 i 个字符不相等. 这时我们需要找下一个需要匹配的位置, 来寻找新位置的前缀函数. 可能会成为新前缀函数值指向的位置的地方, 一定是前缀已经与前 i-1 个字符组成的字符串的某一个后缀相等的地方. 又因为这个新的前后缀长度一定小于上一个前缀函数的值, 所以这个相当于求前缀函数值代表的字符串的前缀函数, 这个是我们已经求过的. 然后继续比较这个前缀函数的前缀函数的后面一个字符是否与新字符相等, 这也一直循环下去直到实在找不到某一个满足条件的前缀后缀, 这时 \pi[i] 等于0.

(反正也没人看 我自己能看懂就行了)

这个算法的复杂度表面上看起来不是 O(n), 因为我们不仅要扫一遍每个字符, 并且在计算每个字符的前缀函数时还要去跳很多次. 但是考虑每一次跳的起点都是上一个字符的前缀函数值, 如果不考虑第一次就匹配成功, 前缀函数值+1的情况, 那么每次起跳的起点就是上一次跳的结束的点, 因为上一次是在前缀函数值处跳结束了才得到的这里就是前缀函数值. 然后考虑第一次匹配成功, 前缀函数值+1的情况. 因为前缀函数值小于等于字符串长度, 所以前缀函数值最多加 N 次, 最后跳的次数还是 O(N) 级别的.

KMP

  1. 当匹配字符串与模式串每次都在第一个字符失配时,暴力算法的效率并不坏.
  2. 暴力算法的可优化之处在于当从某一个字符开始,后面已经与模式串匹配了很多字符,这时如果失配,下一个字符仍然要从模式串的首部开始匹配,浪费了计算资源.
  3. 求出模式串的前缀函数next,当在匹配串的某一位置失配时,可以知道当匹配串指针不动的情况下,模式串应该移动到何处才能让匹配串指针前的模式串与匹配串仍是匹配的.这是一个充分必要的条件,即next数组所求得的移动位置是不会多也不会少的,证明了正确性.由于这样匹配串的指针不会倒退,只会前进,所以匹配过程的复杂度是O(N)的,这时每次从匹配串字符开始匹配时模式串的移动距离就不重要了. (To be continued…)

update: 字符串不是我负责了, 我爬了

评论



本站总访问量为 访客数为