进阶班第一次课

什么是kmp算法?是由Kmp三个人发明的，75年的，扣边界，考coding。

题目

有2个字符串str1长度n,str2长度m，如果str2是str1的子串，求str2在str1中首次出现的位置，否则返回-1.

注： 子串，子数组一定连续，子序列不一定连续。

蛮力法

算法思想：遍历str1的每个字符，判断以它开始的字符串是否与第二个字符串匹配。

时间复杂度：O(mn)

缺点：从str1的哪个字符开始没有关系，也就是没有利用字符串间的位置关系，也没有利用前面的结果。

​ 如果是从i位置开始，则下一次总是从i+1位置开始，kmp不是这样，kmp选一定一个位置j，从j开始，跳过了(i ,j)

kmp

流程

1. 主串遍历指针i1从0(也可以认为从一个非具体的位置i开始)位置开始，子串遍历指针也从0位置开始，一路比较
2. 2个相等同时右移一位，否则看next[i2] == -1 。
   • 如果等于表示i2处于子串第一个字符，此时主串i1位置的字符与子串第一个不等，主串遍历指针i1右移一位；
   • 如果i2不是处于子串第一个字符，则更新i2 = next[i2]（这里本来应该主串有个索引j，主串从j开始，j的位置为不相等的那个字符的位置 - 最长匹配后缀的长度，子串从0开始，因为）

Q1:为什么(i，j)位置上肯定配不出str2？

假设存在k ∈ 0 ~ j，主串从k出发，子串从0出发，可以配出str2。那么k -到X之前的 应该和子串 相等长度的前缀相同，这可能吗？为什么不可能？

• 3和4是匹配的最长前缀和最长后缀
• 如果1 和 2 是相同的，因为 1和 5是相同的（主串i位置到x之前的 和 子串str2 0位置 到 Y之前的都相同），那么==>2和5是相同的，而5比4长，说明找到了一个更长的匹配的最长前缀和最长后缀，这产生了矛盾。

next[i] =** 0 ~ i-1位置上的串 的前缀 和后缀 匹配的 最大长度(不包括长第一个和最后1个字符)，next[0] = -1 ,next[1] = 0.

a b c a b c
0 1 2 3 4 5
next[0] = -1
next[1] = 0
next[2] = 0
next[3] = 0
next[4] = 1
next[5] = 2

next数组怎么求？

next[i]

比较i-1位置上的字符与 前缀 + 1位置上的字符是否相等，

如果相等则next[i] = next[i-1] + 1;(为什么不能更大，采用反证法证明)

如果不相等,如a b a b c a b a b t k