Java教程

字符串算法_前缀函数与 KMP 算法

本文主要是介绍字符串算法_前缀函数与 KMP 算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

原文:https://oi-wiki.org/string/kmp/
此篇为读后总结

  1. 很多字符串算法都是应用 借助之前的计算好的答案来加速计算新的答案。简单来讲就是dp。
  2. 前缀函数pi[i] 意为:以i为结尾的子字符串与原字符串的最长的公共前缀 即s[0~i] 与 s的最长公共前缀的子串的长度 即:s[0~pi[i]] 相等 s[i-pi[i]~i]
  3. 之前计算好的答案为 pi[i]。显而易见的是:如果 s[pi[i]+1] == s[i+1] 那么 pi[i] = pi[i]+1; 利用了pi[i]长度的字符串相等
    如果s[pi[i]+1] != s[i+1] 不相等呢? 那既然 s[0~pi[i]] 与 s[i-pi[i]~i] 相等 那么我就只需要考虑当 s[0~pi[i]]作为整个字符串时,它的最长公共全缀就行了。即: pi[pi[i]]。一直不等的话,就一直这样。

应用

  1. kmp 思路:将p+#+s 作为新字符串,然后求前缀函数
  2. 字符串的周期 思路 pi[n-1] 与 pi[pi[n-1]] .....看值是不是一致
  3. 统计每个前缀的出现次数. 思路:(TODO)
  4. 一个字符串中本质不同子串的数目. 思路:(TODO)
  5. 字符串压缩. 思路:(TODO)
  6. 根据前缀函数构建一个自动机。这个与 https://www.cnblogs.com/kingbuffalo/p/14282210.html 讲的kmp算法.有相似。
这篇关于字符串算法_前缀函数与 KMP 算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!