文档章节

数据结构---->串的模式匹配算法

小强斋太
 小强斋太
发布于 2016/11/09 20:07
字数 1702
阅读 17
收藏 0

字符串模式匹配有着广泛的应用,如求最大公共子串、最长回文字符串、L-Gap、数据压缩、DNA序列匹配等问题。所谓模式匹配就是在目标字符串中寻找第一个子串在目标串中的位置的过程,要寻找的字串即为模式。

        目标 T : Beijing

        模式 P :jin

        匹配结果= 3  

一、BF算法(也叫传统的字符串模式匹配算法、朴素模式匹配、穷举模式匹配)

BF(Bruce Force)算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果。(通俗的解释)

BF(Bruce Force)算法可以说是模式匹配算法中最简单、最容易理解的一个。原理很简单。其基本思想是从主串的start位置开始与模式串进行匹配,如果相等,则继续比较后续字符,如果不相等则模式串回溯到开始位置,主串回溯到start+1位置,继续进行比较直至模式串的所有字符都已比较成功则匹配成功,或者主串所有的字符已经比较完毕,没有找到完全匹配的字串,则匹配失败。(引用别人的解释)

1.1举例说明

    S:  ababcababa

    P:  ababa

BF算法匹配的步骤如下

            i=0                                   i=1                                 i=2                               i=3                              i=4

  第一趟:ababcababa         第二趟:ababcababa      第三趟:ababcababa    第四趟:ababcababa    第五趟:ababcababa

              ababa                              ababa                            ababa                          ababa                          ababa

               j=0                                    j=1                                 j=2                              j=3                              j=4(i和j回溯)

 

              i=1                                   i=2                                  i=3                                i=4                         i=3

第六趟:ababcababa         第七趟:ababcababa       第八趟:ababcababa     第九趟:ababcababa   第十趟:ababcababa

             ababa                                ababa                             ababa                          ababa                          ababa

             j=0                                        j=0                                         j=1                             j=2(i和j回溯)               j=0

 

                      i=4                                    i=5                                 i=6                                 i=7                                 i=8

第十一趟:ababcababa       第十二趟:ababcababa    第十三趟:ababcababa   第十四趟:ababcababa   第十五趟:ababcababa

                       ababa                                  ababa                              ababa                            ababa                            ababa

                       j=0                                        j=0                                     j=1                                   j=2                                   j=3

 

                               i=9

第十六趟:ababcababa

                         ababa

                                 j=4(匹配成功)

1.2参考别人的C代码实现

public class BR_String {

	/**
	 * 
	 * @param s
	 *            主串
	 * @param p
	 *            模式串
	 * @return 模式串在主串中第一次出现的位置,如果找不到则返回-1
	 */
	static int BF(String s, String p) {
		int i = 0, j = 0;

		while (i < s.length())

		{

			j = 0;

			while (j < p.length() && s.charAt(i) == p.charAt(j)) // 如果相等,则继续比较后续字符

			{

				i++;

				j++;

			}

			if (j == p.length())

				return i - p.length();

		   i = i - j + 1; // 指针i回溯

		}

		return -1;
	}

	public static void main(String[] args) {
		String s = "ababcababa";
		String p = "ababa";
		System.out.println(s.indexOf(p));// 用来验证的
		System.out.println(BF(s, p));

	}
}

1.3、第一次看完BF算法的定义以后自己写的代码

以下代码是第一次看完BF算法的定义以后自己写的。和上面基本相同,可能理解起来简单点。以主串为参照,主串的第i个字符和模式串的第一个字符比较,第[i+j]个字符和模式串的第j个字符比较,s[i+j] 和p[j]不相等时候,j变成0,i++,相当于回溯了)

public class BR_String {

	/**
	 * 
	 * @param s
	 *            主串
	 * @param p
	 *            模式串
	 * @return 模式串在主串中第一次出现的位置,如果找不到则返回-1
	 */
	static int BF(String s, String p) {
		int m = s.length() - p.length(); //
		int n = p.length();
		int index = 0; // 记录位置,以便成功时返回字串在主串的位置
		int start = 0;// start为从第start位置的字符开始比较

		while (start < n && index <= m) {

			if (s.charAt(index + start) == p.charAt(start))
				// 如果相等,则继续比较后续字符
				start++;

			else {
				// 如果不相等则模式串回溯到开始位置,主串回溯到start+1位置,继续进行比较;
				index++;
				start = 0;
			}

		}
		if (start == p.length()) {

			return index;
		}

		return -1;
	}

	public static void main(String[] args) {
		String s = "ababcababa";
		String p = "ababa";
		System.out.println(BF(s, p));
		System.out.println(s.indexOf(p));// 用来验证的

	}
}

其实在上面的匹配过程中,有很多比较是多余的。在第五趟匹配失败的时候,在第六趟,i可以保持不变,j值为2。因为在前面匹配的过程中,对于串S,已知s0s1s2s3=p0p1p2p3,又因为p0!=p1!,所以第六趟的匹配是多余的。又由于p0==p2,p1==p3,所以第七趟和第八趟的匹配也是多余的。在KMP算法中就省略了这些多余的匹配。

二、KMP算法

一种由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.Pratt)三人设计的线性时间字符串匹配算法,就取三个人名字的首字母作为该算法的名字可使目标串的检测指针每趟不回退。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题,只需确定下次匹配j的位置即可,使得问题的复杂度由O(mn)下降到O(m+n)。

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

1、失效函数

定义:若设模式 P =p0p1pm-2pm-1

示例:确定失效函数f(j)

 

 

2、利用失效函数 f (j)的匹配处理

如果  j =0,则目标指针加 1,模式指针回到p0

如果 j >0,则目标指针不变,模式指针回到pf(j-1)+1。

public static int KMPMatch(String s, String p) {

		int next[] = getNext(p);
		int i = 0, j = 0;
		while (i < s.length())

		{
			if ((s.charAt(i) == p.charAt(j))) { // 匹配的时候 ,目标串和模式串的指针都后移
				i++;
				j++;
			}

			else if (j == 0) // 不匹配,如果 j=0,相当于和模式串的第0个字符不相等,则目标指针加
								// 1,继续和模式串的第0个字符比较。
				i++;

			else
				j = next[j - 1] + 1; // 不匹配,如果 j>0,则目标指针不变,模式指针回到 next(j-1)+1。

			if (j == p.length())

				return i - p.length();

		}

		return -1;
	}

3、失效函数的求法

1、第一种思路是用递推的思想去求算

public static int[] getNext(String p) {

		int next[] = new int[p.length()];

		next[0] = -1;

		for (int j = 1; j < p.length(); j++) {

			int i = next[j - 1];

			while (p.charAt(i + 1) != p.charAt(j) && i >= 0) //这里搞不明白
				i = next[i];

			if (p.charAt(i + 1) == p.charAt(j))   
				next[j] = i + 1;

			else
				next[j] = -1;
		}

		return next;
	}

2、根据定义直接求解

public static int[] getNext_by_Definition(String p) {

		int next[] = new int[p.length()];

		next[0] = -1;

		for (int j = 1; j < p.length(); j++) {

			int i = j;

			while (i <= j && i > 0) {
				if (p.substring(0, i).equals(p.substring(j - i + 1, j + 1)))

				{
					next[j] = i - 1;
					break;
				}

				else {
					i--;
				}

				if (i == 0)
					next[j] = -1;

			}

		}

		return next;
	} 

 

参考:KMP算法

本文转载自:http://www.cnblogs.com/xqzt/archive/2012/11/13/5637147.html

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
私信 提问
数据结构与算法JavaScript (四) 串(BF)

串是由零个或多个字符组成的有限序列,又叫做字符串 串的逻辑结构和线性表很相似的,不同的是串针对是是字符集,所以在操作上与线性表还是有很大区别的。线性表更关注的是单个元素的操作CUR...

文艺小青年
2017/06/29
0
0
模式匹配算法

《数据结构(C语言版)》上给出了两种模式匹配算法,BF算法和KMP算法。 存在一个主串S和一个模式T,要在主串S中查找与模式T相匹配的子串。 BF算法 操作步骤: 分别利用计数指针和 指示主串和...

流氓兔来啦
2016/11/06
8
0
《数据结构与算法》之KMP算法(15)

当然了,大家如果不熟悉的话,这么看我说这些道理,或者是看我写的代码也是难理解的,所以推荐大家看看《大话数据结构》这本书,这本书里面关于这个KMP算法讲得特别好,我如果再讲也是没人家...

lixiyuan
2014/04/16
0
3
数据结构与算法系列----AC自动机

一:概念 首先简要介绍一下AC自动机:Aho-Corasick automation,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出n个单词,再给出一段文章(长度是m),让...

wangxuwei
02/22
0
0
KMP 字符串匹配经典算法深度解析

摘要:KMP算法是字符串匹配的经典算法,由于其O(m+n)的时间复杂度,至今仍被广泛应用。大道至简,KMP算法非常简洁,然而,其内部却蕴含着玄妙的理论,以至许多人知其然而不知其所以然。本文旨...

红薯
2011/08/10
2.2K
0

没有更多内容

加载失败,请刷新页面

加载更多

分布式锁的实现

redis实现分布式锁 方法1:普通实现方案 实现方式: 使用指令: set key 随机值 ex 5 nx.意思是当key不存在的时候设置key. 如果key存在返回OK,否则返回nil. 实现过程: 1.执行命令set key true ...

grace_233
19分钟前
1
0
解决CKEditor 4 富文本编辑器在图片组件无法显示[上传]选项卡的相关问题

关于解决CKEditor 4 富文本编辑器在图片组件无法显示[上传]选项卡的相关问题。 本文可能会对以下现象得以解决: 图片上传组件,没有 [上传] 选项卡。 资源无法加载 [imgupload] ( Uncaught E...

Eller
23分钟前
0
0
限制php解析、user_agent、php相关配置

11月20日任务 11.28 限定某个目录禁止解析php 11.29 限制user_agent 11.30/11.31 php相关配置 11.28、限定某个目录禁止解析php 核心配置文件内容 <Directory /data/wwwroot/www.123.com/upl...

zgxlinux
28分钟前
1
0
博客园首页新随笔联系订阅管理 随笔

注解Annotation实现原理与自定义注解例子 什么是注解? 对于很多初次接触的开发者来说应该都有这个疑问?Annontation是Java5开始引入的新特征,中文名称叫注解。它提供了一种安全的类似注释的...

onedotdot
45分钟前
4
1
Spring boot + redis 用RedisTemlate实现简单的String key value 操作

springboot集成redis, 简单的key, value缓存操作. 1. application-local.properties # redis on local#spring.redis.port=6379#spring.redis.host=localhost#spring.redis.password=......

园领T
58分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部