字符串 模式匹配

要点

模式匹配是数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出与该子串相同的所有子串,这就是模式匹配

假设P是给定的子串,T是待查找的字符串,要求从T中找出与P相同的所有子串,这个问题成为模式匹配问题。P称为模式,T称为目标。如果T中存在一个或多个模式为P的子串,就给出该子串在T中的位置,称为匹配成功;否则匹配失败。

文中代码是本人自己写的,实测有效,含JAVA和C++两种代码。干货充足吧。

蛮力算法 (BF算法)

蛮力算法(Brute-Force),简称BF算法。(男朋友算法,简单粗暴—_—!)

算法思想

BF算法的算法思想是:

目标串T的的第一个字符起与模式串P的第一个字符比较。

若相等,则继续对字符进行后续的比较;否则目标串从第二个字符起与模式串的第一个字符重新比较。

直至模式串中的每个字符依次和目标串中的一个连续的字符序列相等为止,此时称为匹配成功,否则匹配失败。

通过下图示例,可一目了然:

算法性能

假设模式串的长度是m,目标串的长度是n。

最坏的情况是每遍比较都在最后出现不等,即没变最多比较m次,最多比较n-m+1遍。

总的比较次数最多为m(n-m+1),因此BF算法的时间复杂度为O(mn)。

BF算法中存在回溯,这影响到效率,因而在实际应用中很少采用。

代码

JAVA版本

BF算法之JAVA实现

 1 public class BFMatch {
 2 
 3 static int bfMatch(String target, String pattern) {
 4 int pos = -1;
 5 int i = 0, j = 0, k = 0;
 6 
 7 // 在没找到匹配pattern的子串前,遍历整个target
 8 while (-1 == pos && i < target.length()) {
 9 
10 // 将目标串和模式串逐一比对,如果有不同的则退出
11 while (j < pattern.length() && target.charAt(i) == pattern.charAt(j)) {
12                 i++;
13                 j++;
14             }
15 
16 if (j >= pattern.length()) { // 如果模式串扫描完,说明目标串中含有这个子串
17                 pos = k;
18             } else { // 反之,没有扫描完,则从目标串的下一个字符开始重新逐一比对
19                 j = 0;
20                 k++;
21                 i = k;
22             }
23         }
24 
25 return pos;
26     }
27 
28 public static void print(String target, String pattern, int index) {
29 if (-1 != index) {
30             System.out.format("[%s] is in the Pos = %d of [%s]\n", pattern, index, target);
31         } else {
32             System.out.format("[%s] is not in the [%s]\n", pattern, target);
33         }
34     }
35 
36 public static void main(String[] args) {
37         String target = "Hello World";
38         String pattern = "llo";
39         String pattern2 = "Woe";
40 
41 int index = bfMatch(target, pattern);
42 int index2 = bfMatch(target, pattern2);
43         print(target, pattern, index);
44         print(target, pattern2, index2);
45 
46     }
47 
48 }

C++版本 BF算法之C++实现

 1 #include <iostream>
 2 #include <string>
 3 
 4 using namespace std;
 5 
 6 int bfMatch(string target, string pattern) {
 7 int pos = -1;
 8 int i = 0, j = 0, k = 0;
 9 
10 // 在没找到匹配pattern的子串前,遍历整个target
11 while (-1 == pos && i < (int)target.length()) {
12 
13 // 将目标串和模式串逐一比对,如果有不同的则退出
14 while (j < (int)pattern.length() && target[i] == pattern[j]) {
15             i++;
16             j++;
17         }
18 
19 if (j >= (int)pattern.length()) { // 如果模式串扫描完,说明目标串中含有这个子串
20             pos = k;
21         } else { // 反之,没有扫描完,则从目标串的下一个字符开始重新逐一比对
22             j = 0;
23             k++;
24             i = k;
25         }
26     }
27 
28 return pos;
29 }
30 
31 void print(string target, string pattern, int index) {
32 if (-1 != index) {
33         cout << "[" << pattern << "] is in the Pos = " << index << " of [" << target << "]" << endl;
34     } else {
35         cout << "[" << pattern << "] is not in the [" << target << "]" << endl;
36     }
37 }
38 
39 int main()
40 {
41 string target = "Hello World";
42 string pattern = "llo";
43 string pattern2 = "Woe";
44 
45 int index = bfMatch(target, pattern);
46 int index2 = bfMatch(target, pattern2);
47     print(target, pattern, index);
48     print(target, pattern2, index2);
49 return 0;
50 }

运行结果

[llo] is in the Pos = 2 of [Hello World]
 [Woe] is not in the [Hello World]

KMP算法

Knuth-Morris-Pratt算法(简称KMP),是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的一个改进算法,消除了BF算法中回溯问题,完成串的模式匹配。

算法思想

在BF算法中,用模式串去和目标串的某个子串比较时,如果不全部匹配,就要回溯到起始位置,然后后移。

显然,移回到前面已经比较过的位置,还是不能完全匹配。

KMP算法的思想是,设法利用这个已知信息,跳过前面已经比较过的位置,继续把它向后移,这样就提高了效率。

由此可知,KMP算法其实有两大要点:

(1) 计算跳转位置信息,这里我们称之为部分匹配表。

(2) 后移到指定位置,重新开始匹配。

首先,来看如何获得部分匹配表

为了确定匹配不成功时,下次匹配时 j的位置,引入了next[]数组,next[j]的值表示模式串P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。

这个next 数组叫做部分匹配表

对于next[]数组的定义如下:

对于BF算法中的例子,模式串P=“abcac”,根剧next[j]的定义,可得到下表:

j

0

1

2

3

4

t[j]

a

b

c

a

c

next[j]

-1

0

0

0

1

有了部分匹配表,就可以后移到指定位置

在匹配过程中,若发生不匹配的情况。

如果next[j] >= 0,则目标串的指针 i 不变,将模式串的指针 j 移动到 next[j] 的位置继续进行匹配;

若next[j] = -1,则将 i 右移1位,并将 j 置0,继续进行比较。

以上要点配合下面的示意图理解,效果会更好哦。

算法性能

假设模式串的长度是m,目标串的长度是n。

在KMP算法中求next数组的时间复杂度为O(m),在后面的匹配中因目标串T的下标不用回溯,所以比较次数可记为n。

由此,得出KMP算法的总的时间复杂度O(n+m)

代码

JAVA版本

KMP算法之JAVA实现

 1 public class KMPMatch {
 2 
 3 // 计算部分匹配表
 4 public static int[] getNext(String pattern) {
 5 int j = 0, k = -1;
 6 int[] next = new int[pattern.length()];
 7         next[0] = -1;
 8 while (j < pattern.length() - 1) {
 9 if (-1 == k || pattern.charAt(j) == pattern.charAt(k)) {
10                 j++;
11                 k++;
12                 next[j] = k;
13             } else {
14                 k = next[k];
15             }
16         }
17 
18 return next;
19     }
20 
21 // KMP算法
22 static int kmpMatch(String target, String pattern) {
23 int i = 0, j = 0, index = 0;
24 int[] next = getNext(pattern); // 计算部分匹配表
25 
26 while (i < target.length() && j < pattern.length()) {
27 if (-1 == j || target.charAt(i) == pattern.charAt(j)) {
28                 i++;
29                 j++;
30             } else {
31                 j = next[j]; // 如果出现部分不匹配,获取跳过的位置
32             }
33         }
34 
35 if (j >= pattern.length())
36             index = i - pattern.length(); // 匹配成功,返回匹配子串的首字符下标
37 else
38             index = -1; // 匹配失败
39 
40 return index;
41 
42     }
43 
44 // 打印完整序列
45 public static void printAll(int[] list) {
46 for (int value : list) {
47             System.out.print(value + "\t");
48         }
49         System.out.println();
50     }
51 
52 public static void main(String[] args) {
53         String target = "ababcabcacbab";
54         String pattern = "abcac";
55 int index = kmpMatch(target, pattern);
56         System.out.format("[%s] is in the pos = %d of [%s]", pattern, index, target);
57     }
58 
59 }

C++版本

KMP算法之C++实现

 1 #include <iostream>
 2 #include <string>
 3 
 4 using namespace std;
 5 
 6 const int MAX = 100;
 7 int next[MAX] = {0};
 8 
 9 // 计算部分匹配表
10 void getNext(string pattern) {
11 int j = 0, k = -1;
12     next[0] = -1;
13 while (j < (int)pattern.length() - 1) {
14 if (-1 == k || pattern[j] == pattern[k]) {
15             j++;
16             k++;
17             next[j] = k;
18         } else {
19             k = next[k];
20         }
21     }
22 return;
23 }
24 
25 // KMP算法
26 int kmpMatch(string target, string pattern) {
27 int i = 0, j = 0, index = 0;
28     getNext(pattern); // 计算部分匹配表
29 
30 while (i < (int)target.length() && j < (int)pattern.length()) {
31 if (-1 == j || target[i] == pattern[j]) {
32             i++;
33             j++;
34         } else {
35             j = next[j]; // 如果出现部分不匹配,获取跳过的位置
36         }
37     }
38 
39 if (j >= (int)pattern.length())
40         index = i - pattern.length(); // 匹配成功,返回匹配子串的首字符下标
41 else
42         index = -1; // 匹配失败
43 
44 return index;
45 
46 }
47 
48 void print(string target, string pattern, int index) {
49 if (-1 != index) {
50         cout << "[" << pattern << "] is in the Pos = " << index << " of [" << target << "]" << endl;
51     } else {
52         cout << "[" << pattern << "] is not in the [" << target << "]" << endl;
53     }
54 }
55 
56 int main()
57 {
58 string target = "ababcabcacbab";
59 string pattern = "abcac";
60 int index = kmpMatch(target, pattern);
61     print(target, pattern, index);
62 return 0;
63 }

运行结果

[abcac] is in the pos = 5 of [ababcabcacbab]

参考资料

《数据结构习题与解析》(B级第3版)

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html

相关阅读

欢迎阅读 程序员的内功——算法 系列

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏信数据得永生

JavaScript 编程精解 中文第三版 一、值,类型和运算符

3518
来自专栏凉城

php怎么统计文章字数?

1805
来自专栏专知

Python高效数据分析的8个技巧

【导读】不管是参加Kaggle比赛,还是开发一个深度学习应用,第一步总是数据分析,这篇文章介绍了8个使用Python进行数据分析的方法,不仅能够提升运行效率,还...

883
来自专栏小詹同学

Leetcode打卡 | No.22 括号生成

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

561
来自专栏数据结构与算法

18:验证子串

18:验证子串 总时间限制: 1000ms 内存限制: 65536kB描述 输入两个字符串,验证其中一个串是否为另一个串的子串。 输入输入两个字符串, 每...

3444
来自专栏猿人谷

一个正则表达式测试(只可输入中文、字母和数字)

  在项目中碰到了正则表达式的运用,正则还是非常强大的,不管什么编程语言,基本上都可以用到。之前在用java时特别是对用户名或密码使用正则非常爽,写脚本上用正则...

3046
来自专栏Code_iOS

Objective-c 知识总结 -- 继承

观察发现,它们属性和方法声明是相同的,都有 填充色(fillcolor)、尺寸+位置(bounds)、绘制方法;

781
来自专栏CodingBlock

Java数据结构和算法总结-字符串相关高频面试题算法

前言:周末闲来无事,在七月在线上看了看字符串相关算法的讲解视频,收货颇丰,跟着视频讲解简单做了一下笔记,方便以后翻阅复习同时也很乐意分享给大家。什么字符串在算...

2600
来自专栏灯塔大数据

每周学点大数据 | No.9递归——以阶乘为例

No.9期 递归——以阶乘为例 Mr. 王:我们介绍一个在计算机算法设计和程序设计中都非常常见的概念——递归。 小可:什么是递归呢? Mr. 王:从程序设计的...

3264
来自专栏java学习

面试题7(考察运算符的优先级)

请选择下面代码运行后打印的结果。 public static void main(String[]args){ int x=5; int y=3; x=x+(x...

2858

扫码关注云+社区