关键词：

title: 串的模式匹配算法之kmp

tags: 数据结构与算法之美

author: 辰砂

1.引言

首先我们需要了解串的模式算法目的：确定主串中所含子串第一次出现的位置（定位）；常见的算法种类： BF算法（又称古典的、经典的、朴素的、穷举的），KMP算法（特点：速度快）。网上有很多帖子，博客写的都特别好，这篇文章也是对自己的一个总结。

2.BF算法

BF算法设计思想：

将主串的第pos个字符和模式的第一个字符比较
若相等，继续逐个比较后续字符；
若不等，从主串的下一字符起，重新与模式的第一个字符比较。
直到主串的一个连续子串字符序列与模式相等 。
返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。
否则，匹配失败，返回值 0

1.举例：

假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？

如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：

如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；

如果失配（即S[i]! = P[j]），令i = i - (j - 1) （表示主串的位置回到当前的下一个位置），j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

1. public static int bfMatch(char[] s, char[] p) 
   int sLen = s.length;
   int pLen = p.length;
   int i = 0;
   int j = 0;
   while (i < sLen && j < pLen) 
   if (s[i] == p[j]) 
   //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++
   i++;
   j++;
    else 
   //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0
   // i - (j - 1) 表示主串的位置回到当前的下一个位置。
   i = i - j + 1;
   j = 0;
   
   
   //匹配成功，返回模式串p在文本串s中的位置，否则返回-1
   if (j == pLen) 
   return i - j;
    else 
   return -1;
   
   
   public static void main(String[] args) 
   String s = "BBC ABCDAB ABCDABCDABDE";
   String p = "ABCDABD";
   System.out.println(bfMatch(s.toCharArray(),p.toCharArray()));
   

    

2.时间复杂度说明：

若n为主串长度，m为子串长度，最坏情况是 主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次 最后m位也各比较了1次

总次数为：(n-m)m+m＝(n-m+1)m 若m<<n，则算法复杂度o(n*m)< p="">

网上有个很好的例子，故引用：

举个例子，如果给定文本串S“BBC ABCDAB ABCDABCDABDE”，和模式串P“ABCDABD”，现在要拿模式串P去跟文本串S匹配，整个过程如下所示：

1.S[0]为B，P[0]为A，不匹配，执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[1]跟P[0]匹配，相当于模式串要往右移动一位（i=1，j=0）

2.S[1]跟P[0]还是不匹配，继续执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[2]跟P[0]匹配（i=2，j=0），从而模式串不断的向右移动一位（不断的执行“令i = i - (j - 1)，j = 0”，i从2变到4，j一直为0）

3.直到S[4]跟P[0]匹配成功（i=4，j=0），此时按照上面的暴力匹配算法的思路，转而执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，可得S[i]为S[5]，P[j]为P[1]，即接下来S[5]跟P[1]匹配（i=5，j=1）

4.S[5]跟P[1]匹配成功，继续执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，得到S[6]跟P[2]匹配（i=6，j=2），如此进行下去

5.直到S[10]为空格字符，P[6]为字符D（i=10，j=6），因为不匹配，重新执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，相当于S[5]跟P[0]匹配（i=5，j=0）

6.至此，我们可以看到，如果按照暴力匹配算法的思路，尽管之前文本串和模式串已经分别匹配到了S[9]、P[5]，但因为S[10]跟P[6]不匹配，所以文本串回溯到S[5]，模式串回溯到P[0]，从而让S[5]跟P[0]匹配。

而S[5]肯定跟P[0]失配。为什么呢？因为在之前第4步匹配中，我们已经得知S[5] = P[1] = B，而P[0] = A，即P[1] != P[0]，故S[5]必定不等于P[0]，所以回溯过去必然会导致失配。那有没有一种算法，让i 不往回退，只需要移动j 即可呢？

3.KMP算法（主串指针不回溯）

算法思想：利用已经部分匹配的结果而加快模式串的滑动速度？且主串S的指针i不必回溯！可提速到O(n+m)！

算法步骤： 下面先直接给出KMP的算法流程：

假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置

如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；

如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。

换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文的3.3.3节中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。

很快，你也会意识到next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。

此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。

public static int kmpMatch(char[] s, char[] p) 
int sLen = s.length;
int pLen = p.length;
int i = 0;
int j = 0;
while (i < sLen && j < pLen) 
if (s[i] == p[j]) 
//①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++
i++;
j++;
 else 
j = next[j];


//匹配成功，返回模式串p在文本串s中的位置，否则返回-1
if (j == pLen) 
return i - j;
 else 
return -1;

为此,定义next[j]函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。

1.如何求next()?

1.寻找前缀后缀最长公共元素长度

比如 字符串 ‘a’ 的前缀就是为空，后缀也是为空，所以前缀后缀的意思，是不包括当前字符串，字符串 ‘ab’ 的前缀是a，后缀是b。

定义： 对于P = p0 p1 ...pj-1 pj，寻找模式串P中长度最大且相等的前缀和后缀。如果存在p0 p1 ...pk-1 pk = pj- k pj-k+1...pj-1 pj，那么在包含pj的模式串中有最大长度为k+1的相同前缀后缀。

比如：

2.求next数组

next 数组考虑的是除当前字符外的最长相同前缀后缀，所以通过第①步骤求得各个前缀后缀的公共元素的最大长度后，只要稍作变形即可：将第①步骤中求得的值整体右移一位，然后初值赋为-1，如下表格所示：

3.如何求next函数值

1. next[1] = 0;表明主串从下一字符si+1起和模式串重新开始匹配。i = i+1; j = 1;

    

2. 设next[j] = k，则next[j+1] = ?

    

   ①若pk=pj，则有“p1…pk-1pk”=“pj-k+1…pj-1pj” ，如果在 j+1发生不匹配，说明next[j+1] = k+1 = next[j]+1。

    

   ②若pk≠pj，可把求next值问题看成是一个模式匹配问 题，整个模式串既是主串，又是子串。

    

   

若pk’=pj，则有“p1…pk’”=“pj-k’+1…pj”， next[j+1]=k’+1=next[k]+1=next[next[j]]+1.

若pk”=pj ，则有“p1…pk””=“pj-k”+1…pj”， next[j+1]=k”+1=next[k’]+1=next[next[k]]+1. next[j+1]=1.

4.总结

核心的点在于：以前的bf算法是需要i进行回溯，导致时间复杂度O(m*n) ,现在kmp算法的核心是i不进行回溯，而j这个值不确定，根据串的规律，主串前面匹配成功的串前缀和后缀相等的地方不需要匹配即可。这样的时间复杂度是O(m + n)

引用博客例子：

1.最开始匹配时

P[0]跟S[0]匹配失败

所以执行“如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]”，所以j = -1，故转而执行“如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++”，得到i = 1，j = 0，即P[0]继续跟S[1]匹配。

P[0]跟S[1]又失配，j再次等于-1，i、j继续自增，从而P[0]跟S[2]匹配。

P[0]跟S[2]失配后，P[0]又跟S[3]匹配。

P[0]跟S[3]再失配，直到P[0]跟S[4]匹配成功，开始执行此条指令的后半段：“如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++”。

2.P[1]跟S[5]匹配成功，P[2]跟S[6]也匹配成功, ...，直到当匹配到P[6]处的字符D时失配（即S[10] != P[6]），由于P[6]处的D对应的next 值为2，所以下一步用P[2]处的字符C继续跟S[10]匹配，相当于向右移动：j - next[j] = 6 - 2 =4 位。

3.向右移动4位后，P[2]处的C再次失配，由于C对应的next值为0，所以下一步用P[0]处的字符继续跟S[10]匹配，相当于向右移动：j - next[j] = 2 - 0 = 2 位。

4.移动两位之后，A 跟空格不匹配，模式串后移1 位。

5.P[6]处的D再次失配，因为P[6]对应的next值为2，故下一步用P[2]继续跟文本串匹配，相当于模式串向右移动 j - next[j] = 6 - 2 = 4 位。

6.匹配成功，过程结束。

匹配过程一模一样。也从侧面佐证了，next 数组确实是只要将各个最大前缀后缀的公共元素的长度值右移一位，且把初值赋为-1 即可。

代码如下：

void get_next(SString T, int &next[])

i= 1; next[1] = 0; j = 0;
while( i<T[0])
if(j==0 || T[i] == T[j])
++i; ++j;
next[i] = j;

else
j = next[j];

kMP算法的时间复杂度

设主串s的长度为n,模式串t长度为m,在KMP算法中求next数组的时间复杂度为O(m),在后面的匹配中因主串s的下标不减即不回溯,比较次数可记为n,所以KMP算法总的时间复杂度为O(n+m)

参考原文：https://blog.csdn.net/vjulyv/article/details/7041827?utm_source=copy

数据结构串---kmp模式匹配算法之获取next数组(代码片段)

...式串T的j下标对目标串S的i值失配时，我们应该使用模式串的下标为next[j]接着去和目标串失配的i值进行匹配而KMP算法的next求值函数我们可以知道next除了j=1时，next[1]为0，其他情况都是比较前缀和后缀串的相似度（第三种情况是... 查看详情

4.2串的模式匹配算法(代码片段)

 <?phpheader("content-type:text/html;charset=utf-8");classLinear_string/***串模式匹配算法**包括*1.串的初始化__contruct()*2.朴素的模式匹配算法index()*3.KMP模式匹配算法*4.改进的KMP模式匹配算法*/private$string;private$length;//构造函数p 查看详情

串的模式之kmp算法实践题(代码片段)

给定两个由英文字母组成的字符串String和Pattern，要求找到Pattern在String中第一次出现的位置，并将此位置后的String的子串输出。如果找不到，则输出“NotFound”。本题旨在测试各种不同的匹配算法在各种数据情况下的表现。... 查看详情

串串的模式匹配算法（子串查找）bf算法kmp算法(代码片段)

串的定长顺序存储#defineMAXSTRLEN255,//超出这个长度则超出部分被舍去，称为截断串的模式匹配：串的定义：0个或多个字符组成的有限序列S=‘a1a2a3…….an‘n=0时为空串串的顺序存储结构：字符数组，串的长度就是数组末尾‘ 查看详情

kmp算法(代码片段)

...法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。原理匹配模式串会 查看详情

kmp算法(代码片段)

数据结构_串对于串,今天就总结了一个算法,关于字符串的模式匹配问题(重点在于kmp算法).普通的模式匹配算法,当匹配不成功时需要将主串的下标恢复到之前匹配的下一个字符,子串下标置为串首;而kmp算法则不需要重置主串的下标... 查看详情

（原创）数据结构之利用kmp算法解决串的模式匹配问题(代码片段)

...baba输出样例:在这里给出相应的输出。例如：6解题思路：串的模式匹配有两种：一种是BF算法，一种是KMP算法；基于这道题给的数据，若用BF算法便会超时，所以我们这道题用KMP算法；那么问题来了，KMP算法到底怎么用的；简单... 查看详情

kmp算法总结(代码片段)

...复杂度降到了O（m+n）。原理是用一个next数组预处理了主串的局部匹配信息（最长相同前后缀长度），在进行主串与模式串的匹配时，保证了主串一直往后遍历不回溯，仅改变指向模式串的指针位置。 【算法原理详解】来看 查看详情

实现顺序串的各种模式匹配算法(代码片段)

目的：掌握串的模式匹配算法（BF和KMP）设计内容：编写一个程序exp4-3.cpp，实现顺序串的各种模式匹配运算，并在此基础上完成以下功能:1、建立目标串s="abcabcdabcdeabcdefabcdefg"和模式串t="abcdeabcdefab"；2、采用简单匹... 查看详情

kmp算法浅谈(代码片段)

...思想在主串和模式串进行匹配时，利用next数组不改变主串的匹配指针而是改变模式串的匹配指针，减少大量的重复匹配时间。在Kmp算法中，next数组的构建是整个Kmp算法的核心所在。二.Kmp核心之next数组的构建（1）前缀，后缀的... 查看详情

数据结构—串kmp模式匹配算法(代码片段)

数据结构—串串顺序串代码实现串的模式匹配BF算法代码实现KMP算法代码实现求next数组的代码KMP算法代码改进代码求nextVal修正的KMP算法串串(string)是由零个或多个字符组成的有限序列。含零个字符的串称为空串,用Ø表示。串中所... 查看详情

❤️详解kmp算法(代码片段)

...核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next数组实现，next数组本身包含了模式串的局 查看详情

串的模式匹配算法------kmp算法(代码片段)

1#include<stdio.h>2#include<stdlib.h>3#include<string.h>45int*get_next(chart[],intlength)67inti=0,j=-1;8int*next=(int*)malloc(length*sizeof(int));9next[0]=-1;10while(i<length)1112if(j==-1||t[i]==t[j])1314i++;15j++;16next[i]=j;1718else1920j=next[j];21222324returnnext;252627intInd... 查看详情

c_cpp串的匹配算法和kmp算法(代码片段)

查看详情

第四章：2.串--串的模式匹配算法（kmp）

前言：　　 目录：　　1.串类型的定义　　2.串的表示和实现　　3.串的模式匹配算法　　4.串操作应用举例 正文：　　串的模式匹配即，在给定主串S中，搜索子串T的位置，如果存在T则返回其所在位置，否则返回0　　串... 查看详情

kmp算法详解及其java实现(代码片段)

...串模式匹配算法，可以在O(n+m)的时间复杂度以内完成字符串的匹配操作，其核心思想在于：当一趟匹配过程中出现字符不匹配时，不需要回溯主串的指针，而是利用已经得到的“部分匹配”，将模式串尽可能多地向右“滑动”一... 查看详情

数据结构与算法之深入解析kmp算法的核心原理和实战演练(代码片段)

...核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本 查看详情

字符串匹配----kmp算法(代码片段)

...法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。先来看看暴力解法：　　假设主串是目... 查看详情