**KMP： 当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。** --- **1 前缀表记录信息：用来回退，它记录了模式串与主串不匹配的时，模式串应该从哪里开始重新匹配。** > 举例： 在主串aabaabaafa 中查找是否出现过一个模式串aabaaf。 可以看出，主串中第6个字符b 和模式串的第6个字符f，不匹配了。如果暴力匹配，发现不匹配，此时就要从头匹配了。 但若使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第3个字符b继续开始匹配。 **总结，前缀表：记录下标i之前（包括i）的字符串中最大长度的相同前缀后缀。** --- **2 如何计算前缀表** 下述例子中，字符串的前缀是指不包含最后一个字符的，所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的，所有以最后一个字符结尾的连续子串。 > 举例： 那么，aabaaf的前缀表： - 长度为前1个字符的子串a，最长相同前后缀的长度为0。 - 长度为前2个字符的子串aa，最长相同前后缀的长度为1。 - 长度为前3个字符的子串aab，最长相同前后缀的长度为0。 - 长度为前4个字符的子串aaba，最长相同前后缀的长度为1。 - 长度为前5个字符的子串aabaa，最长相同前后缀的长度为2。 - 长度为前6个字符的子串aabaaf，最长相同前后缀的长度为0。 可以看出，模式串与前缀表对应位置的值就是：下标i之前（包括i）的字符串中，最大长度的相同前缀后缀。 --- 时间复杂度分析 **O(n+m)** - 其中n为主串长度，m为模式串长度 - 在匹配的过程中，根据前缀表不断调整匹配的位置匹配的过程是O(n) - 之前还要单独生成next数组，时间复杂度是O(m) 暴力的解法是O(n × m)，所以KMP在字符串匹配中极大地提高了搜索的效率。 --- 代码如下 ```python class Solution: def strStr(self, haystack: str, needle: str) -> int: n = len( haystack ) m = len( needle ) if m == 0: return 0 if n < m : return -1 # KMP nextval = [ 0 for _ in range( n ) ] def init_nextval(): # > i 指向后缀末尾 # > j 指向前缀末尾 # > 示例: aabaaf j = 0 # i从1开始 因为nextvalue[ 0 ]就是0 ( 最大相同前后缀 不包含自身 ) for i in range( 1, m ): # 后缀末尾和前缀末尾不同 向前回退确定现在的前缀末尾 # nextval[j - 1 ]记录着之前的子串的相同前后缀的长度。 # 逐次向前寻找是否needle[ j ]==needle[ i ]重新确定j # 如果始终没发现最终j为0 则可以从j继续比较 避免重复计算 while j > 0 and needle[ j ] != needle[ i ]: j = nextval[ j - 1 ] # 前缀和后缀的末尾相等 相同前后缀增加 前缀末尾后移 if needle[ j ] == needle[ i ]: j += 1 # 最终确定[ 0, i ]的最大相同前后缀 nextval[ i ] = j init_nextval() # > j 指向当前的needle[ j ] # > i 指向当前的haystack[ i ] j = 0 for i in range( 0, n ): while j > 0 and haystack[ i ] != needle[ j ]: # 对比时 在needle[ j ]处发现不匹配 # 没有必要将j还原0从头开始比对 # nextval[j - 1 ]记录着之前的子串的相同前后缀的长度。通过该信息还原位置 防止重复比较 j = nextval[ j - 1 ] # 相同时 匹配长度增加 needle 已经匹配的位置变更 if haystack[ i ] == needle[ j ]: j += 1 if j == m: return i - m + 1 return -1 ``` --- 详细注释 ```python class Solution: def strStr(self, haystack: str, needle: str) -> int: # KMP n = len( haystack ) m = len( needle ) # 1 <= haystack.length, needle.length <= 10e4 if m > n: return -1 """ 初始化nextval 以方便回退 """ nextval = [ 0 for _ in range( m ) ] def init_nextval(): j = 0 # j指向相同前缀末尾 for i in range( 1, m ): # i指向相同后缀末尾 while j > 0 and needle[ j ] != needle[ i ]: # 相同前缀末尾变化 但也不是直接就回到0 尝试已经匹配的有没有位置可以继续对比 j = nextval[ j - 1 ] if needle[ j ] == needle[ i ]: j += 1 nextval[ i ] = j init_nextval() """ 主串和模式串匹配 """ j = 0 # 匹配成功的模式串尾部 for i in range( n ): # 主串的尾部 while j > 0 and haystack[ i ] != needle[ j ]: # j不用从头开始 或许可以从某个位置继续向后匹配 j = nextval[ j - 1 ] if haystack[ i ] == needle[ j ]: j += 1 if j == m: return i - m + 1 return -1 ```