c++ kmp算法字符匹配_LeetCode笔记：字符串匹配——KMP算法

KMP算法是一种字符串匹配算法，用于在一个文本串S内查找一个模式串P的出现位置。它的时间复杂度为O(n+m)，其中n为文本串的长度，m为模式串的长度。

KMP算法的核心思想是利用已知信息来避免不必要的字符比较。具体来说，它维护一个next数组，其中next[i]表示当第i个字符匹配失败时，下一次匹配应该从模式串的第next[i]个字符开始。

我们可以通过一个简单的例子来理解KMP算法的思想。假设文本串为S="ababababca"，模式串为P="abababca"，我们想要在S中查找P的出现位置。

首先，我们可以将P的每个前缀和后缀进行比较，得到next数组：

| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| --- | - | - | - | - | - | - | - | - |
| P | a | b | a | b | a | b | c | a |
| next| 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

接下来，我们从S的第一个字符开始匹配P。当S的第七个字符和P的第七个字符匹配失败时，我们可以利用next[6]=4，将P向右移动4个字符，使得P的第五个字符与S的第七个字符对齐。此时，我们可以发现P的前五个字符和S的前五个字符已经匹配成功了。因此，我们可以继续从S的第六个字符开始匹配P。

当S的第十个字符和P的第八个字符匹配失败时，我们可以利用next[7]=1，将P向右移动一个字符，使得P的第一个字符和S的第十个字符对齐。此时，我们可以发现P的前一个字符和S的第十个字符已经匹配成功了。因此，我们可以继续从S的第十一个字符开始匹配P。

最终，我们可以发现P出现在S的第二个位置。

下面是KMP算法的C++代码实现：