字符串 模式匹配

要点

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

假设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 条评论
登录 后参与评论

相关文章

来自专栏决胜机器学习

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一)——图的连通性问题与最小生成树算法(2) (原创内容,转载请注明来源,谢谢) 再次遇到微信公众号限制字数3000字的问题。因此将...

36210
来自专栏和蔼的张星的图像处理专栏

28. 搜索二维矩阵二分法

写出一个高效的算法来搜索 m × n矩阵中的值。 这个矩阵具有以下特性: 每行中的整数从左到右是排序的。 每行的第一个数大于上一行的最后一个整数。 样例...

612
来自专栏苦逼的码农

从0打卡leetcode之day 6--最长回文串

对于这道题,最简单的方法就是暴力求解了。对于很多算法题,我想会暴力求解是最基本的能力,但也绝不能满足于暴力,而且很多题的暴力解法都是很类似的。

823
来自专栏决胜机器学习

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(六)——数组的相乘、广义表 (原创内容,转载请注明来源,谢谢) 本文接PHP数据结构(五)的内容。 4.2 行逻辑链接的顺序表 行逻辑链接的顺...

3689
来自专栏向治洪

图算法之bfs、dfs、prim、Dijkstra

概述 在图算法中经常要执行遍历每个顶点和每条边的操作,即图搜索。许多图算法都以图搜索为基础,如2-着色问题、连通性计算基于深度优先搜寻(depth-first ...

2566
来自专栏tkokof 的技术,小趣及杂念

数学小记之数系

自然数即非负整数(包括 0 和 正整数),字母表示为 N(Natural number) :

764
来自专栏fangyangcoder

leetcode(二)

给定一个二叉数(root),二叉树中一个node(target)以及整数K,求二叉树中所有与target距离K的节点值。问题描述与example如下。

682
来自专栏积累沉淀

hash算法原理详解

一.概念 哈希表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。 哈希的思路很简单,如果所有...

3965
来自专栏数说工作室

【SAS Says】基础篇:5. 开发数据(一)

本节目录: 开发数据 5.1 创建并重新定义变量 5.2 使用SAS函数 5.3 使用IF-THEN语句 5.4 用IF-THEN语句将观测值分组 5.5 构造...

3054
来自专栏F_Alex

数据结构与算法(七)-树

前言:回顾一下前面学习的内容,大概说了下数据结构中的线性结构,从物理存储方面来说又分为顺序存储和链式存储结构,各自有自己的优缺点,顺序存储结构读快写慢,链式存储...

903

扫码关注云+社区