【复试上机】LeetCode-简单-010-Implement strStr

Implement strStr()

文字思想：

就是KMP算法，数据结构知识点课程详细讲过，不再详细解释。

求next数组核心思想：

 a)依次去求next数组【依次去求重合】。

 b)求重合的过程其实就是模式匹配过程【利用已经求得的next数组】。

 c)next[indexS+1] = indexC+1。

为了效率更高，next数组可以进一步优化为nextVal数组。

 a)在next数组基础上进行改进,nextVal[1] = 0。

 b)求next数组时，是直接 next[indexS] = indexC,这里多一步判断就好，indexS位置上的字符与indexC位置上字符:

     不等：nextVal[indexS] = indexC

     相等：nextVal[indexS] = nextVal[indexC]

KMP算法核心思想：

 a)框架与简单匹配差不多,区别是在与不匹配时,不匹配时，模式串查找next数组，确定跳转位置。

 b)最终模式串遍历到尾、主串任意：匹配;主串到尾、模式串没到尾：不匹配。

代码：

复杂度：

就是KMP算法的时间复杂度O(m+n)，m是模式串的长度，n是主串的长度。

空间复杂度O(m)，nextVal数组的长度。

积累：

KMP算法本身。

注：

如果使用暴力方法解，也扣不了多少分，先有答案，再考虑优化的问题。