2.10 日学习总结

今天来做一下kmp算法的题目解答。 具体题目如下，是一个标准的模板题。
  
算法思想有两个点。一个就是next数组的建立。另一个就是next 数组的使用。 那么什么是next 数组呢？ 他就是给一个字符串的每一个位置记录下在这个点时前面字符串的最大前后缀长度。那我们为什么要求这么一个数组？这就在于一个匹配问题。上面也给了一个解释。 就是当你匹配两个字符串是否相等时。如果当你匹配到不同你就要重新匹配。你当然可以选择。一开始退后一格，然后再进行匹配。但是这样的做法是十分需要时间的。而kmp算法就是进行了一个问题的转化。要做的就是。在你进行匹配当中出现不匹配的情况。他要你做的是寻找在你匹配的子字符串中他的前面还有多少能接上这个母字符串在这一个位置时的后缀。而能做到这一点的原因就是你在这一格不适配。那么你前面的所有都是匹配成功的。那么对于你这个子字符串来说，在不匹配的这一个前面的所有字符就是你要匹配的母字符串中的所含字符。也就是你所需要的后缀。而我们拥有一个next数组，他记录下了在这一位的最大前后缀长度。因此我们就可以直接通过这个数组。找到最大

2.10 日学习总结最先出现在Python成神之路。