代码随想录算法训练营day 9：KMP算法，字符串匹配

KMP算法

KMP算法是一个字符串匹配算法，用来在一个主串中高效地查找模式串第一次（或所有）出现的位置。简要概括其思想就是主串永远向前走，模式串永远有策略地重新对齐。

如果用暴力解，每次回退主串指针都会很耗时，显然，为了单单一个字符的匹配失败而回退整个模式串指针和主串指针显然不划算。所以KMP核心思想是：当匹配失败时，不回退主串指针，而是有策略地移动模式串指针。

KMP 的核心突破点

利用已匹配的信息：当模式串匹配到s[ i ]失败时，比较指针回退到：从s[0]到s[i - 1]这段模式串中，前缀与后缀相同的最长长度之后的那个字符。

为什么？这段模式串的某个前缀与某个后缀相同，说明不用回退整个模式串，直接让模式串的前缀与主串已匹配的后缀对齐（因为已经说明它们相等），这样，主串永远向前走，模式串永远有策略地重新对齐。

怎么知道匹配失败模式串到哪里重新对齐呢？记录在s[0]到s[i - 1]这段模式串中的前后缀相同的最长长度，用一个next数组，next[ i ]存储下标0到下标 i - 1 的前后缀信息。假设next[ i ] = n，则前n个字符已经默认匹配成功，所以从这个长度的后面一个字符开始即可。

相关习题

LeetCode 28.找出字符串中第一个匹配项的下标

LeetCode 459.重复的子字符串