大话数据结构 java_【Java】大话数据结构(8) 串的模式匹配算法（朴素、KMP、改进算法）...

快来打我* 2022-11-04 15:24 130阅读 0赞

本文根据《大话数据结构》一书，实现了Java版的串的朴素模式匹配算法、KMP模式匹配算法、KMP模式匹配算法的改进算法。

1.朴素的模式匹配算法

为主串和子串分别定义指针i，j。

(1)当 i 和 j 位置上的字母相同时，两个指针都指向下一个位置继续比较；

(2)当 i 和 j 位置上的字母不同时，i 退回上次匹配首位的下一位，j 则返回子串的首位。

![d3a599d9e1150885db04bc7af7349847.png][](注：该图从下标为1开始 )

实现程序：

/\*\*

\* 朴素的模式匹配算法

\* 说明：下标从0开始，与书稍有不同，但原理一样

\* @author Yongh

\*/

public class BruteForce \{

/\*

\* 返回子串t在主串s中第pos个字符后的位置。若不存在返回-1

\*/

int index(String s,String t,int pos) \{

int i=pos; //i为主串位置下标

int j=0; //j为子串位置下标

while(i

if(s.charAt(i)==t.charAt(j)) \{

i++;

j++; //i和j指向下一个位置继续比较

\}else \{ /\*重新匹配\*/

i=i-j+1; //退回上次匹配首位的下一位

j=0; //返回子串的首位

if(j==t.length()) \{

return i-j;

\}else \{

return -1;

public static void main(String\[\] args) \{

BruteForce sample =new BruteForce();

int a= sample.index("goodgoogle", "google", 0);

System.out.println(a);

![8f900a89c6347c561fdf2122f13be562.png][]

![961ddebeb323a10fe0623af514929fc1.png][]

BruteForce

2.KMP模式匹配算法

2.1 KMP模式匹配算法的主体思路

![f4144349ab3d3e65baa598d675a875fa.png][]

在上图的比较中，当 i 和 j 等于5时，两字符不匹配。在朴素匹配算法中，会令i=1，j=0，然后进行下一步比较；但是，我们其实已经知道了i=1到4的主串情况了，没有必要重复进行i=2到4的比较，且我们观察“ABCABB”的B前面的ABCAB，其前缀与后缀(黄色部分)相同，所以可以直接进行上图中的第三步比较(令 i 不变，令 j 从5变成2，继续进行比较)。这就是KMP模式匹配算法的大概思路。这当中的 j 从5跳转到了2，2通过一个函数next(5)求得，next(5)即代表j=5位置不匹配时要跳转的下一个进行比较的位置。

KMP模式匹配算法：

为主串和子串分别定义指针 i 和 j 。

(1)当 i 和 j 位置上的字母相同时，两个指针都指向下一个位置继续比较；

(2)当 i 和 j 位置上的字母不同时，i 不变，j 则返回到next\[j\]位置重新比较。(暂时先不管next\[\]的求法，只要记得定义有next\[0\]=-1)

(3)当 j 返回到下标为0时，若当 i 和 j 位置上的字母仍然不同，根据(2)，有 j = next\[0\]=-1，这时只能令i 和 j 都继续往后移一位进行比较 (同步骤(1))。

上述内容可结合下图说明：

![f4144349ab3d3e65baa598d675a875fa.png][]

(1)i 和 j 从下标为0开始比较，该位置两字母相同，i 和 j 往后移继续比较；

(2)一直比较到 i 和 j 等于5时，两字母不同， i 不变，j 返回到 next\[j\]的位置重新比较，该子串的next\[5\]=2，所以 j 返回到下标为2的位置继续与 i=5的主串字母比较。

(3)在下图情况下，当j=0时，两字母不同，子串只能与主串的下一个元素比较了(即i=1与j=0比较)。根据(2)，会使 j=next\[j\]=next\[0\]=-1，所以现在的i=0，j=next\[0\]=-1了，要下一步比较的话两个指针都要加一。

![1a3b1fd20bd61cd6f936b8862e1ff894.png][]

![53c0f6ec8461b8b6dda952cd084839de.png][]

![c44e5a5a47d24d369b50c3c7185a4c05.png][]

根据上述说明可以写出如下代码(代码中的next\[\]暂时假设已知，之后会讲)：

/\*

\* 返回子串t在主串s中第pos个字符后的位置(包含pos位置)。若不存在返回-1

\*/

public int index\_KMP(String s, String t, int pos) \{

int i = pos; //主串的指针

int j = 0; //子串的指针

int\[\] next = getNext(t); //获取子串的next数组

while (i < s.length() && j < t.length()) \{

if (j == -1 || s.charAt(i) == t.charAt(j)) \{

// j==-1说明了子串首位也不匹配，它是由上一步j=next\[0\]=-1得到的。

i++;

j++;

\} else \{

j = next\[j\];

if (j == t.length())

return i - j;

return -1;

2.2 next\[\]的定义与求解

根据上述内容可知，next\[j\] 的含义为：当下标为 j 的元素在不匹配时，j 要跳转的下一个位置下标。

继续结合下图说明：

![f4144349ab3d3e65baa598d675a875fa.png][]

当j=5时，元素不匹配，j跳转到next\[5\]=2的位置重新比较。

那为什么next\[5\]的值为2呢？即，为什么j=5不匹配时要跳转到2位置呢？

观察 ABCABB这个字符串，下标为5的字符为B，它前面的字符 ABCAB 与主串完全相同，而ABCAB的前缀与后缀(黄色部分)相同，，所以前缀AB不用再进行比较了，直接比较C这个字符，即下标为2的字符，所以next\[5\]=2。

那么该如何求解跳转位置next\[\]呢？通过刚才的讨论，我们可以发现next\[j\]的值等于 j 位置前面字符串的相同前后缀的最大长度，上面例子就是等于AB的长度2。

next\[\]的公式如下：

![8cbf133c955a6ecd99b9aa0acee81979.png][]

公式说明：

1.在j=0时，0位置之前没有字符串，next\[0\]定义为-1 ；

2. 在 j 位置之前的字符串中，如果有出现前后缀相等的情况，令 j 变为相等部分的最大长度，即刚刚所说的相同前后缀的最大长度。如上述的ABCABB字符串中，j=5时，前面相等部分AB长度为2，所以next\[5\]=2；

3.其余情况下，next\[j\]=0。其他情况，没有出现字符的前后缀相等，相同前后缀的最大长度自然就是0。

那求解next\[\]的代码如何实现呢？以下是代码的分析过程：

1.定义两个指针 i=0 和 j=-1，分别指向前缀和后缀( j 值始终要比 i 值小)，用于确定相同前后缀的最大长度；(因为 i 是后缀，所以我们求的都是 i+1位置的next值next\[i+1\])

2.根据定义有：next\[0\]=-1;

3.当前缀中 j 位置的字符和后缀中 i 位置的字符相等时，说明 i+1 位置的next值为 j+1 (因为 j+1 为相同前后缀的最大长度，可结合下面两种情况思考)(即next\[i+1\]=j+1)

![fb1ec70facbdd744415c6aec5e1aff3c.png][]

![cd80831ea6f177f43730066b8fc08938.png][]

4.j==-1时，说明前缀没有与后缀相同的地方，最大长度为0，则 i+1 位置的next值只能为0，此时也可以表示为next\[i+1\]=j+1。

5.当 j 位置的字符和 i 位置的字符不相等时，说明前缀在第 j 个位置无法与后缀匹配，令 j 跳转到下一个匹配的位置，即j= next\[j\] 。

以下是实现求解next\[\]的程序：

/\*

\* 返回字符串的next数组

\*/

public int\[\] getNext(String str) \{

int length = str.length();

int\[\] next = new int\[length\]; //别忘了初始化

int i = 0; //i为后缀的指针

int j = -1; //j为前缀的指针

next\[0\] = -1;

while (i < length - 1) \{ // 因为后面有next\[i++\],所以不是i

if (j == -1 || str.charAt(i) == str.charAt(j)) \{ // j == -1代表前后缀没有相等的部分,i+1位置的next值为0

next\[++i\] = ++j; //等于前缀的长度

\} else \{

j = next\[j\];

return next;

2.3 KMP完整代码

结合next数组的求解和KMP算法，完整代码如下：

import java.util.Arrays;

/\*\*

\* KMP模式匹配算法

\* 返回子串t在主串s中第pos个字符后的位置。若不存在返回-1 要注意i不变，只改变j

\* @author Yongh

\*/

public class KMP \{

/\*

\* 返回字符串的next数组

\*/

public int\[\] getNext(String str) \{

int length = str.length();

int\[\] next = new int\[length\]; //别忘了初始化

int i = 0; //i为后缀的指针

int j = -1; //j为前缀的指针

next\[0\] = -1;

while (i < length - 1) \{ // 因为后面有next\[i++\],所以不是i

if (j == -1 || str.charAt(i) == str.charAt(j)) \{ // j == -1代表前后缀没有相等的部分,i+1位置的next值为0

next\[++i\] = ++j; //等于前缀的长度

\} else \{

j = next\[j\];

return next;

/\*

\* 返回子串t在主串s中第pos个字符后的位置(包含pos位置)。若不存在返回-1

\*/

public int index\_KMP(String s, String t, int pos) \{

int i = pos; //主串的指针

int j = 0; //子串的指针

int\[\] next = getNext(t); //获取子串的next数组

while (i < s.length() && j < t.length()) \{

if (j == -1 || s.charAt(i) == t.charAt(j)) \{

// j==-1说明了子串首位也不匹配，它是由j=next\[0\]=-1得到的。

i++;

j++;

\} else \{

j = next\[j\];

if (j == t.length())

return i - j;

return -1;

public static void main(String\[\] args) \{

KMP aKmp = new KMP();

System.out.println(Arrays.toString(aKmp.getNext("BBC")));

System.out.println(Arrays.toString(aKmp.getNext("ABDABC")));

System.out.println(Arrays.toString(aKmp.getNext("ababaaaba")));

System.out.println(aKmp.index\_KMP("goodgoogle", "google", 0));

![8f900a89c6347c561fdf2122f13be562.png][]

![961ddebeb323a10fe0623af514929fc1.png][]

\[-1, 0, 1\]

\[-1, 0, 0, 0, 1, 2\]

\[-1, 0, 0, 1, 2, 3, 1, 1, 2\]4

KMP

2.4 一道题目

已知字符串S为abaabaabacacaabaabcc,模式串P为abaabc。采用KMP算法进行匹配，第一次出现“失配”(S\[i\]≠P\[j\])时，i=j=5,则下次开始匹配时，i和j的值分别是：C。

A. i= 1, j = 0B. i= 5, j = 0C.i= 5, j = 2D. i= 6, j = 2

分析：模式串就是之前所说的子串，i 和 j 是之前所说的指针。根据刚刚的分析中，出现失配时，指针 i 是不会变动的，只会变 j，j=next\[j\]。next\[j\]的物理意义是 j 位置前面字符串的相同前后缀的最大长度，我们可以发现abaabc中c前面的字符串中相同前后缀为ab,长度为2，所以直接可以选出答案为C。

3.KMP模式匹配算法改进

对于如下字符串，j=3时，next\[j\]=1，根据next的定义，即当 j=3位置不匹配时，j跳转到1位置重新比较，但可以发现，j=2位置和j=1位置其实是同一个字母，没有必要重复比较。

![fd62e9120d02e0595b6d92feff6ab115.png][]

举个例子，在KMP算法下的比较过程如下(按图依次进行)：

![c21b140d1cf28c1cb59c157bf55e87bd.png][]

![d448dc6e458e51a204cf81d254696adb.png][]

![ed28a6cfe762a526c68064102408af3a.png][]

因为有next\[3\]=1，所以会出现中间这个其实可以省略掉的过程。实际上我们是可以直接跳到j=0那一步进行比较的，这就需要修改next数组，我们把新的数组记为nextval数组。

中间那步可以省略是因为，j=3和 j=1位置上的字符是完全相同的，因此没有必要再进行比较了。因此只需要在原有的next程序中加上一个字符是否相等的判断，如果要跳转的nextval位置上的字符于当前字符相等，令当前字符的nextval值等于要跳转位置上的nextval值。

![efe1ea9217645b42e14f68bfebdfc776.png][]

KMP模式匹配算法的改进程序如下:

import java.util.Arrays;

/\*\*

\* KMP模式匹配算法 的改进算法

\* 返回子串t在主串s中第pos个字符后的位置。若不存在返回-1 要注意i不变，只改变j

\* @author Yongh

\*/

public class KMP2 \{

/\*

\* 返回字符串的next数组

\*/

public int\[\] getNextval(String str) \{

int length = str.length();

int\[\] nextval = new int\[length\];

int i = 0; //i为后缀的指针

int j = -1; //j为前缀的指针

nextval\[0\] = -1;

while (i < length - 1) \{

if (j == -1 || str.charAt(i) == str.charAt(j)) \{

i++;

j++;

if(str.charAt(i)!=str.charAt(j)) \{ //多了一个字符是否相等的判断

nextval\[i\] = j; //等于前缀的长度

\}else \{

nextval\[i\]=nextval\[j\];

\} else \{

j = nextval\[j\];

return nextval;

/\*

\* 返回子串t在主串s中第pos个字符后的位置(包含pos位置)。若不存在返回-1

\*/

public int index\_KMP(String s, String t, int pos) \{

int i = pos; //主串的指针

int j = 0; //子串的指针

int\[\] next = getNextval(t); //获取子串的next数组

while (i < s.length() && j < t.length()) \{

if (j == -1 || s.charAt(i) == t.charAt(j)) \{

// j==-1说明了子串首位也不匹配，它是由j=next\[0\]=-1得到的。

i++;

j++;

\} else \{

j = next\[j\];

if (j == t.length())

return i - j;

return -1;

public static void main(String\[\] args) \{

KMP2 aKmp = new KMP2();

System.out.println(Arrays.toString(aKmp.getNextval("BBC")));

System.out.println(Arrays.toString(aKmp.getNextval("ABDABC")));

System.out.println(Arrays.toString(aKmp.getNextval("ababaaaba")));

System.out.println(aKmp.index\_KMP("goodgoogle", "google", 0));

![8f900a89c6347c561fdf2122f13be562.png][]

![961ddebeb323a10fe0623af514929fc1.png][]

\[-1, -1, 1\]

\[-1, 0, 0, -1, 0, 2\]

\[-1, 0, -1, 0, -1, 3, 1, 0, -1\]4

KMP2

改进的算法仅在第24到28行代码发生了改变。

![18c5abe3c392ff46bc2cf603512695d5.png][]

图中这句话可以结合下表仔细体会。(要记得nextval\[j\]的含义：j位置的字符未匹配时要跳转的下一个位置)

![a3d83903c41f30050e26b2f12b2d9da1.png][]

附：

要记住上面的算法，一定要记住指针 i 和 j 代表的意义，j==-1的意义，以及next的意义。

(getNext()中前缀位置和后缀位置，index\_KMP()中主串位置和子串位置)，(前缀或子串的首个字符就无法匹配)，(要跳转的下一个位置)

还有要注意的就是，i为后缀，我们求的是下一个位置的next值，即next\[i+1\]。

[d3a599d9e1150885db04bc7af7349847.png]: /images/20221023/e8c2310221d942efbe4b612e3b3a6963.png
[8f900a89c6347c561fdf2122f13be562.png]: /images/20221023/78ed459c93d44361a92dc7ee8c60ae81.png
[961ddebeb323a10fe0623af514929fc1.png]: /images/20221023/feb993e980bf4521ac5d54920299974a.png
[f4144349ab3d3e65baa598d675a875fa.png]: /images/20221023/dc9d8a18d39d431695f2954c58324b69.png
[1a3b1fd20bd61cd6f936b8862e1ff894.png]: /images/20221023/8d4f62ae13f748daad5c18f775269945.png
[53c0f6ec8461b8b6dda952cd084839de.png]: /images/20221023/a46d81de5a4e4b70839907b807225d20.png
[c44e5a5a47d24d369b50c3c7185a4c05.png]: /images/20221023/6618c424556849a39b7c07c9b422aae8.png
[8cbf133c955a6ecd99b9aa0acee81979.png]: /images/20221023/86b5855e19b74fd4ad6e6fde435e782f.png
[fb1ec70facbdd744415c6aec5e1aff3c.png]: /images/20221023/4f6d9ecfab50439f8fea14e0df60b26a.png
[cd80831ea6f177f43730066b8fc08938.png]: /images/20221023/375309fc20cd4df299c12660b21ccf95.png
[fd62e9120d02e0595b6d92feff6ab115.png]: /images/20221023/35079751165243609d25526356e05566.png
[c21b140d1cf28c1cb59c157bf55e87bd.png]: /images/20221023/a7458a0e669b47268d1fd1090c420a79.png
[d448dc6e458e51a204cf81d254696adb.png]: /images/20221023/47d15a7a06ca432884420baee5b8e9a4.png
[ed28a6cfe762a526c68064102408af3a.png]: /images/20221023/f6f257ee4a264916af401435d8cb6d1a.png
[efe1ea9217645b42e14f68bfebdfc776.png]: /images/20221023/7f44b80b89ed4b59bbdcbf1f9a618ff7.png
[18c5abe3c392ff46bc2cf603512695d5.png]: /images/20221023/9237ca3b570945ec860ceb41dcd27cb3.png
[a3d83903c41f30050e26b2f12b2d9da1.png]: /images/20221023/ff47f5f73ccd49bf898ac72819c203f1.png