KMP算法

kmp算法例题KMP算法是一种字符串匹配算法，用于在一个文本串S内查找一个模式串P的出现位置。

举个例子，如果文本串S为'ABCABCABC'，模式串P为'ABC'，那么KMP算法会返回3个匹配位置，分别为0、3和6。

KMP算法的核心是利用模式串的信息来避免在文本串中不必要的比较。

具体来说，KMP算法维护一个next数组，用于记录模式串的前缀和后缀的最长公共长度。

在匹配过程中，如果一个字符与模式串不匹配，那么可以跳过一定长度的字符，直接比较后面的字符。

下面是一个KMP算法的示例代码：```vector<int> getNext(string p) {int n = p.size();vector<int> next(n, 0);int j = 0;for (int i = 1; i < n; i++) {while (j > 0 && p[i] != p[j]) {j = next[j - 1];}if (p[i] == p[j]) {j++;}next[i] = j;}return next;}vector<int> kmp(string s, string p) { int n = s.size(), m = p.size();vector<int> ans;if (m == 0) {return ans;}vector<int> next = getNext(p);int j = 0;for (int i = 0; i < n; i++) {while (j > 0 && s[i] != p[j]) {j = next[j - 1];}if (s[i] == p[j]) {j++;}if (j == m) {ans.push_back(i - m + 1);j = next[j - 1];}}return ans;}```上面的代码中，getNext函数用于计算next数组，kmp函数用于查找模式串在文本串中的出现位置。

KMP算法是一种字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。

它的核心思想是利用已经匹配过的部分信息，尽量减少不必要的比较。

KMP算法的公式如下：1. 预处理模式串，得到next数组：-初始化next数组，next[0] = -1，next[1] = 0；-从第2个字符开始，依次计算next[i]的值：-如果模式串的前缀和后缀匹配，即pattern[j] == pattern[i-1]，则next[i] = j + 1；-如果模式串的前缀和后缀不匹配，即pattern[j] != pattern[i-1]，则需要回溯到前一个可能的匹配位置，即j = next[j]，直到找到一个匹配位置或者回溯到起始位置；-如果回溯到起始位置仍然没有找到匹配位置，则next[i] = 0。

2. 在主串中查找模式串：-初始化主串指针i = 0，模式串指针j = 0；-依次比较主串和模式串的字符：-如果主串和模式串的字符匹配，即text[i] == pattern[j]，则继续比较下一个字符；-如果主串和模式串的字符不匹配，即text[i] != pattern[j]，则需要根据next数组回溯模式串的指针j，即j = next[j]，直到找到一个匹配位置或者回溯到起始位置；-如果回溯到起始位置仍然没有找到匹配位置，则主串指针i和模式串指针j都向后移动一位，继续比较下一个字符；-如果模式串指针j移动到模式串的末尾，则表示找到了一个匹配位置，返回匹配位置的起始索引；-如果主串指针i移动到主串的末尾，则表示没有找到匹配位置，返回-1。

KMP算法通过预处理模式串得到next数组，利用next数组的信息在匹配过程中尽量减少不必要的比较，提高了匹配效率。

kmp算法概念KMP算法概念KMP算法是一种字符串匹配算法，它的全称是Knuth-Morris-Pratt 算法。

该算法通过预处理模式串，使得在匹配过程中避免重复比较已经比较过的字符，从而提高了匹配效率。

一、基本思想KMP算法的基本思想是：当模式串与文本串不匹配时，不需要回溯到文本串中已经比较过的位置重新开始匹配，而是利用已知信息跳过这些位置继续匹配。

这个已知信息就是模式串自身的特点。

二、next数组1.定义next数组是KMP算法中最核心的概念之一。

它表示在模式串中当前字符之前的子串中，有多大长度的相同前缀后缀。

2.求解方法通过观察模式串可以发现，在每个位置上出现了相同前缀和后缀。

例如，在模式串“ABCDABD”中，第一个字符“A”没有任何前缀和后缀；第二个字符“B”的前缀为空，后缀为“A”；第三个字符“C”的前缀为“AB”，后缀为“B”；第四个字符“D”的前缀为“ABC”，后缀为“AB”；第五个字符“A”的前缀为“ABCD”，后缀为“ABC”；第六个字符“B”的前缀为“ABCDA”，后缀为“ABCD”；第七个字符“D”的前缀为“ABCDAB”，后缀为“ABCDA”。

根据上述观察结果，可以得到一个求解next数组的方法：（1）next[0]=-1，next[1]=0。

（2）对于i=2,3,...,m-1，求解next[i]。

①如果p[j]=p[next[j]]，则next[i]=next[j]+1。

②如果p[j]≠p[next[j]]，则令j=next[j]，继续比较p[i]和p[j]。

③重复执行步骤①和步骤②，直到找到满足条件的j或者j=-1。

（3）通过上述方法求解出所有的next值。

三、匹配过程在匹配过程中，文本串从左往右依次与模式串进行比较。

如果当前字符匹配成功，那么继续比较下一个字符；否则利用已知信息跳过一些位置继续进行匹配。

具体地：（1）如果当前字符匹配成功，则i和j都加1。

（2）如果当前字符匹配失败，则令j=next[j]。

KMP算法（改进的模式匹配算法）——next函数KMP算法简介KMP算法是在基础的模式匹配算法的基础上进⾏改进得到的算法，改进之处在于：每当匹配过程中出现相⽐较的字符不相等时，不需要回退主串的字符位置指针，⽽是利⽤已经得到的部分匹配结果将模式串向右“滑动”尽可能远的距离，再继续进⾏⽐较。

在KMP算法中，依据模式串的next函数值实现字串的滑动，本随笔介绍next函数值如何求解。

next[ j ]求解将 j-1 对应的串与next[ j-1 ]对应的串进⾏⽐较，若相等，则next[ j ]=next[ j-1 ]+1;若不相等，则将 j-1 对应的串与next[ next[ j-1 ]]对应的串进⾏⽐较，⼀直重复直到相等，若都不相等则为其他情况题1在字符串的KMP模式匹配算法中，需先求解模式串的函数值，期定义如下式所⽰，j表⽰模式串中字符的序号（从1开始）。

若模式串p 为“abaac”，则其next函数值为（）。

解：j=1，由式⼦得出next[1]=0；j=2，由式⼦可知1<k<2，不存在k，所以为其他情况即next[2]=1；j=3，j-1=2 对应的串为b，next[2]=1，对应的串为a，b≠a，那么将与next[next[2]]=0对应的串进⾏⽐较，0没有对应的串，所以为其他情况，也即next[3]=1；j=4，j-1=3 对应的串为a，next[3]=1，对应的串为a，a=a，所以next[4]=next[3]+1=2；j=5，j-1=4 对应的串为a，next[4]=2，对应的串为b，a≠b，那么将与next[next[4]]=1对应的串进⾏⽐较，1对应的串为a，a=a，所以next[5]=next[2]+1=2；综上，next函数值为 01122。

题2在字符串的KMP模式匹配算法中，需先求解模式串的函数值，期定义如下式所⽰，j表⽰模式串中字符的序号（从1开始）。

若模式串p为“tttfttt”，则其next函数值为（）。

KMP算法详解KMP 算法详解KMP 算法是⼀个⼗分⾼效的字符串查找算法，⽬的是在⼀个字符串 s 中，查询 s 是否包含⼦字符串 p，若包含，则返回 p 在 s 中起点的下标。

KMP 算法全称为 Knuth-Morris-Pratt 算法，由 Knuth 和 Pratt 在1974年构思，同年 Morris 也独⽴地设计出该算法，最终由三⼈于1977年联合发表。

举⼀个简单的例⼦，在字符串 s = ababcabababca 中查找⼦字符串 p = abababca，如果暴⼒查找，我们会遍历 s 中的每⼀个字符，若 s[i] = p[0]，则向后查询p.length() 位是否都相等。

这种朴素的暴⼒的算法复杂度为O(m×n)，其中m和n分别是 p 和 s 的长度。

KMP 算法可以⽅便地简化这⼀查询的时间复杂度，达到O(m+n)。

1. PMT 序列PMT 序列是 KMP 算法的核⼼，即 Partial Match Table（部分匹配表）。

举个例⼦：char a b a b a b c aindex01234567PMT00123401PMT 的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。

PMT[0] = 0: 字符串 a 既没有前缀，也没有后缀；PMT[1] = 0: 字符串 ab 前缀集合为 {a}，后缀集合为 {b}，没有交集；PMT[2] = 1: 字符串 aba 前缀集合为 {a, ab}，后缀集合为 {ba, a}，交集为 {a}，交集元素的最长长度为1；PMT[3] = 2: 字符串 abab 前缀集合为 {a, ab, aba}，后缀集合为 {bab, ab, b}，交集为 {ab}，交集元素的最长长度为2；…… 以此类推。

2. 算法主体现在我们已经知道了 PMT 序列的含义，那么假设在 PMT 序列已经给定的情况下，如何加速字符串匹配算法？tar 存储 s 的下标，从 0 开始，若 tar > s.length() - 1，代表匹配失败；pos 存储 p 的下标，从 0 开始，若 s[tar] != p[pos]，则 pos ⾛到下⼀个可能匹配的位置。

KMP算法简介什么是KMP算法KMP算法（Knuth-Morris-Pratt算法）是一种用于字符串匹配的算法，用于在一个主串中查找一个模式串的出现位置。

它的特点是在匹配失败时，不回溯主串的指针，而是通过利用已经匹配过的信息，将模式串尽量地向后移动，从而提高匹配效率。

KMP算法的原理KMP算法的核心思想是利用模式串自身的特点，通过预处理模式串，构建一个部分匹配表（Partial Match Table），从而在匹配过程中可以根据已匹配的信息来决定下一步的匹配位置。

部分匹配表部分匹配表是一个与模式串对应的数组，用于存储模式串在每个位置上的最长相同前缀后缀的长度。

例如，对于模式串”ABCDABD”，其部分匹配表为：位置部分匹配值0 01 02 03 04 15 26 0KMP算法的匹配过程KMP算法的匹配过程可以简述为以下几个步骤：1.预处理模式串，构建部分匹配表；2.在主串中从左到右逐个字符进行匹配；3.如果当前字符匹配成功，则继续比较下一个字符；4.如果当前字符匹配失败，则根据部分匹配表，将模式串向右移动一定的距离，再次进行匹配；5.重复步骤3和4，直到模式串匹配完毕或者主串匹配完毕。

KMP算法的优势相较于朴素的字符串匹配算法，KMP算法具有以下优势：1.减少了不必要的字符比较次数，提高了匹配效率；2.通过预处理模式串，可以在匹配过程中根据已匹配的信息决定下一步的匹配位置，避免了回溯主串的指针。

KMP算法的应用KMP算法在字符串匹配中有着广泛的应用，例如：1.字符串查找：在一个文本中查找一个子串的出现位置；2.字符串替换：将一个文本中的某个子串替换为另一个字符串；3.DNA序列匹配：在生物信息学中，用于比对DNA序列的相似性。

KMP算法的压力测试为了验证KMP算法的效率和稳定性，我们进行了一系列的压力测试。

测试环境•操作系统：Windows 10•处理器：****************************•内存：16GB测试方法我们使用不同长度的主串和模式串进行匹配，记录下KMP算法的执行时间，并与朴素的字符串匹配算法进行对比。

KMP算法-易懂版⼀：定义 Knuth-Morris-Pratt 字符串查找算法，简称为 KMP算法，常⽤于快速查找⼀个母串S中是否包含⼦串(模式串)P，以及P出现的位置。

由于简单的暴⼒匹配中，每次遇到不匹配的位置时都要回溯到母串上⼀次的起点 i +1的位置上再次从⼦串的开头进⾏匹配，效率极其低下，故⽽KMP算法应运⽽⽣，减少回溯过程中不必要的匹配部分，加快查找速度。

⼆：kmp算法求解步骤描述 若当前不匹配的位置发⽣在母串位置 i，⼦串位置 j 上，则：1. 寻找⼦串位置 j 之前元素的最长且相等的前后缀，即最长公共前后缀。

记录这个长度。

2. 根据这个长度求 next 数组3. 若 j != 0, 则根据next [j] 中的值，将⼦串向右移动，也就是将公共前缀移到公共后缀的位置上，(代码表⽰为：j=next [j]，注意 i 不变)，即对位置 j 进⾏了更新，后续⼦串直接从更新后的 j 位置和母串 i 位置进⾏⽐较。

4. 若 j == 0，则 i+1，⼦串从j位置开始和母串 i+1 位置开始⽐较。

综上，KMP的next 数组相当于告诉我们：当⼦串中的某个字符跟母串中的某个字符匹配失败时，⼦串下⼀步应该跳到哪个位置开始和母串当前失配位置进⾏⽐较。

所以kmp算法可以简单解释为：如⼦串在j 处的字符跟母串在i 处的字符失配时，下⼀步就⽤⼦串next [j] 处的字符继续跟⽂本串 i 处的字符匹配，相当于⼦串⼀次向右移动 j - next[j] 位，跳过了⼤量不必要的匹配位置(OK，简单理解完毕之后，下⾯就是求解KMP的关键步骤，Let’s go! ) 三：kmp算法关键步骤之⼀，求最长的公共前后缀！ 箭头表⽰当前匹配失败的位置，也就是当前的 j 位置。

⽩框表⽰最长公共前后缀AB！此时长度为2！ 再来⼀个，此时最长公共前后缀为ABA！长度为3！四：kmp算法关键步骤之⼆，求next[ ] 数组 由步骤⼀，我们可以得到⼦串每个位置前⾯元素的最长共同前后缀，注意⼦串第⼀个位置是没有前后缀的，所以长度为0！ 例：⼦串ABCDABD的最长公共前后缀可表⽰如下。

kmp next算法KMP算法（Knuth-Morris-Pratt Algorithm）是一种字符串匹配算法，它的核心思想是利用已经得到的匹配结果，尽量减少字符的比较次数，提高匹配效率。

本文将详细介绍KMP算法的原理、实现方法以及应用场景。

一、KMP算法的原理KMP算法的核心是构建next数组，用于指导匹配过程中的回溯操作。

next数组的定义是：对于模式串中的每个字符，记录它前面的子串中相同前缀和后缀的最大长度。

next数组的长度等于模式串的长度。

具体来说，KMP算法的匹配过程如下：1. 初始化主串指针i和模式串指针j为0。

2. 逐个比较主串和模式串对应位置的字符：- 若主串和模式串的字符相等，i和j同时后移一位。

- 若主串和模式串的字符不相等，根据next数组的值，将模式串指针j回溯到合适的位置，继续匹配。

二、KMP算法的实现KMP算法的实现可以分为两个步骤：构建next数组和利用next数组进行匹配。

1. 构建next数组：- 首先，next[0]赋值为-1，next[1]赋值为0。

- 然后，从第2个位置开始依次计算next[i]，根据前一个位置的next值和模式串的字符进行判断：- 若前一个位置的next值为-1或模式串的字符与前一个位置的字符相等，则next[i] = next[i-1] + 1。

- 若前一个位置的next值不为-1且模式串的字符与前一个位置的字符不相等，则通过next数组的回溯操作，将模式串指针j回溯到合适的位置，继续判断。

2. 利用next数组进行匹配：- 在匹配过程中，主串指针i和模式串指针j会同时后移：- 若主串和模式串的字符相等，i和j同时后移一位。

- 若主串和模式串的字符不相等，则根据next数组的值，将模式串指针j回溯到合适的位置，继续匹配。

三、KMP算法的应用场景KMP算法在字符串匹配中有广泛的应用，特别是在大规模文本中的模式匹配问题上具有明显的优势。

以下是KMP算法的几个应用场景：1. 子串匹配：判断一个字符串是否是另一个字符串的子串。

字符串匹配kmp算法字符串匹配是计算机科学中的一个基本问题，它涉及在一个文本串中寻找一个模式串的出现位置。

其中，KMP算法是一种更加高效的算法，它不需要回溯匹配过的字符，在匹配失败的时候，根据已经匹配的字符和模式串前缀的匹配关系直接跳跃到下一次匹配的起点。

下面，我将详细介绍KMP算法原理及其实现。

1. KMP算法原理KMP算法的核心思想是：当模式串中的某个字符与文本串中的某个字符不相同时，根据已经匹配的字符和模式串前缀的匹配关系，跳过已经比较过的字符，从未匹配的字符开始重新匹配。

这个过程可以通过计算模式串的前缀函数（即next数组）来实现。

具体地，假设现在文本串为T，模式串为P，它们的长度分别为n和m。

当对于文本串T的第i个字符和模式串P的第j个字符（i和j都是从0开始计数的）进行匹配时：如果T[i]和P[j]相同，则i和j都加1，继续比较下一个字符；如果T[i]和P[j]不同，则j回溯到next[j]（next[j]是P[0]到P[j-1]的一个子串中的最长的既是自身的前缀又是后缀的子串的长度），而i不会回溯，继续和P[next[j]]比较。

如果匹配成功，则返回i-j作为P在T中的起始位置；如果匹配失败，则继续执行上述过程，直到文本串T被遍历完或匹配成功为止。

2. KMP算法步骤（1）计算模式串的前缀函数next[j]。

next[j]表示P[0]到P[j-1]的一个子串中的最长的既是自身的前缀又是后缀的子串的长度。

具体计算方式如下：先令next[0]=-1，k=-1（其中k表示相等前缀的长度，初始化为-1），j=0。

从j=1向后遍历整个模式串P：如果k=-1或者P[j]=P[k]，则next[j+1]=k+1，k=j，j+1；否则，令k=next[k]，再次执行步骤2。

（2）使用next数组进行匹配。

从文本串T的第0个字符开始，从模式串P的第0个字符开始匹配，如果匹配失败，根据next数组进行回溯。

KMP算法KMP算法是一种用于字符串匹配的快速算法，全称为Knuth-Morris-Pratt算法，是由Donald Knuth、Vaughan Pratt和James Morris在1977年共同提出的。

该算法的核心思想是通过利用已经匹配过的部分来避免不必要的字符比较，从而提高匹配效率。

1.暴力匹配算法在介绍KMP算法之前，我们先来了解一下暴力匹配算法。

暴力匹配算法，又称为朴素匹配算法，是最基本的匹配方法，它的思想就是从主串的第一个字符开始，逐个比较主串和模式串的字符，直到匹配成功或者主串和模式串的所有字符都比较完毕。

具体算法如下：```暴力匹配(主串S,模式串P)：i=0j=0n = length(S)m = length(P)while i < n and j < m:if S[i] == P[j]: // 匹配成功，继续比较下一个字符i++else: // 匹配失败，模式串向后移动一位i=i-j+1j=0if j == m: // 匹配成功return i - jelse: // 匹配失败return -1```暴力匹配算法的时间复杂度为O(n*m)，其中n和m分别为主串和模式串的长度。

2.KMP算法的思想KMP算法的关键在于构建一个部分匹配表，通过这个表来确定模式串在匹配失败时应该移动的位置。

部分匹配表的定义如下：对于模式串P的前缀子串P[0:i]，如果存在一个真前缀等于真后缀，则称其长度为i的真前缀的真后缀长度为部分匹配值。

假设有一个模式串P，我们定义一个部分匹配表next，其中next[i]表示在P[i]之前的子串(不包括P[i])中，有多大长度的相同前缀后缀。

例如，P="ABCDABD"，则next[7]=2，因为在P[7]之前的子串中，"ABD"是长度为3的前缀，也是长度为3的后缀。

构建部分匹配表的算法如下：构建部分匹配表(P):m = length(P)next = [0] * m // 初始化部分匹配表j=0k=-1next[0] = -1while j < m - 1:if k == -1 or P[j] == P[k]: // P[j]表示后缀的单个字符，P[k]表示前缀的单个字符j++k++next[j] = kelse:k = next[k]```构建部分匹配表的时间复杂度为O(m)，其中m为模式串的长度。