2021.12.21 硬刚KMP算法
28. 实现 strStr()
459. 重复的子字符串
686. 重复叠加字符串匹配
今天刷的题基本上都是KMP算法的，正好借这个机会好好学习一下这个算法。
28. 实现 strStr()
KMP算法，主要用于在字符串匹配，即在一个长的字符串中查找一个给定的字符串是否存在。同时这也是今天的第一道题28. 实现 strStr()。
遇到这样的问题，首先想到的就是暴力解法，用两个指针分别指向两字符串的首位，然后不断进行匹配比较，如果匹配不成功的话，就在长的字符串上的下一位进行比较，这一步是必要的，因为不能确定由下一位开始的字符串中是否包含了子串，这样算法的时间复杂度是O(mn)，因为在最差情况下要对长字符串的每一位进行匹配一次。而使用KMP算法就可以将时间复杂度减小到O(m + n)。
其实在使用暴力解法时，很容易想到如果不是每一次都在长串中选择下一位进行比较，因为有时后面的位也已经进行了比较，这样就可以选择下一个有可能的位置，直接跳过中间不可能的位置，大大降低算法复杂度。
于是这样就诞生了KMP算法。KMP算法通过一个辅助数组next保存子串的信息，next数组中每一位表示从子串开头到当前位的字符串的最大相同前缀后缀的长度。因为存储了这样的信息，当子串与长串进行匹配时，如果匹配不成功，就可以利用next的信息直接跳过已经比较的部分继续比较。
比如，在要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。子串aabaaf的next数组是[0, 1, 0, 1, 2, 0]。当比较到aabaab与aabaaf时，由于b和f不相同，所以停止比较，选择子串当前位置的前一位，获得next数组中该位的值也就是2，我们这时直接选择子串的索引为2的位，也就是b那一位与当前长串中匹配到的位进行匹配，并最终获得匹配成功的结果。
在next数组中存储了最长相等前缀后缀的长度，所以当匹配到的b与f不同时，之前匹配过的子串aabaa与长串完全相同，所以我们可以选择最长的相同前缀，也就是子串开始的aa，与上面匹配过的b后面的aa进行匹配，由于这两部分一定相同，直接从下一位开始继续匹配，这样就在O(n)的时间复杂度下完成了匹配。
构建next数组的过程，与匹配的过程类似，主要就是使用双指针来解一个字符串当前子串的最长相等前缀后缀。使用两个指针j,i分别指向0和1的位置，当ij指向的值相同时，j++; next[i] = j; 当不同时，j取前一位next[j - 1]，然后继续与i比较，直到相等或者j取到0。这样遍历一遍子串就可以获得next数组，所以总的时间复杂度就是O(m + n)。
在写代码时，生成next数组和匹配的部分差不太多，不同的是在生成next数组时是自己跟自己比较，匹配的时候是两个字符串之间相互比较。当匹配完最后一位的时候停止循环。具体代码就不在这写了。
459. 重复的子字符串
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。如果不是刚刚写了KMP算法的题，估计这题我也不会写。如果直接暴力判断的话，枚举子串长度，这样算法复杂度太高。但是结合刚刚学过的KMP算法的知识，这到题就可以转化成使用KMP算法求next数组的思想来求解。
如果一个字符串可以通过子串重复若干次进行生成，那生成的next数组尾部会形成每次 + 1的规律，在最后一位会获得一个值，这个值加上子串的长度正好等于整个字符串的长度。这块还没太理解，明天再想想。
686. 重复叠加字符串匹配
给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。
这道题正好是今天的每日一题，也同样是利用KMP算法来进行匹配，首先计算b的长度然后将a重复若干次，直到a的长度大于等于b的长度，这时对两个字符串进行匹配，如果不能在a里找到b，就再加上一个a再匹配一次，如果仍然匹配不到的话就说明匹配不到了，返回-1.
