文档章节

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

小强斋太
 小强斋太
发布于 2016/11/09 20:07
字数 1702
阅读 17
收藏 0
点赞 0
评论 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
数据结构与算法JavaScript (五) 串(经典KMP算法)

KMP算法和BM算法 KMP是前缀匹配和BM后缀匹配的经典算法,看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同 前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从 左到右...

文艺小青年
2017/06/01
0
0
数据结构与算法之KMP算法02

一、KMP算法思路启发2 1.深入探讨算法思路 这次我们给模式匹配串添加一个K数组(也就是KMP算法中非著名的next数组); 这是一个"智能"的数组,因为他指导着模式匹配串下一步改用第几号元素去...

aibinxiao
前天
0
0
字符串匹配算法KMP详细解释——深入理解

1. 前言   字符串匹配是一个经典算法问题,展开来讲各类问题多达几十种,有名称的算法也不下三十种,所以需要深入学习的东西有很多。这次我们来探讨一个最简单的问题,假设现在随机输入一个...

fx677588
2016/12/04
0
0
从头到尾彻底理解KMP(2014年8月15日版)

从头到尾彻底理解KMP 作者:July 时间:最初写于2011年12月,2014年7月21日晚10点 全部删除重写成此文,随后的半个多月不断反复改进。 1. 引言 本KMP原文最初写于2年多前的2011年12月,因当时...

Michael-W
2014/08/17
0
0
数据结构 第8讲 KMP算法

数据结构 第8讲 KMP算法 讲这个算法之前,我们首先了解几个概念: 串:又称字符串,是由零个或多个字符组成的有限序列。如S="abcdef" 子串:串中任意个连续的字符组成的子序列,称为该串的子...

rainchxy
2017/10/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

MyBatis入门

一、安装 <dependency> <groupId>org.mybatis</groupId> <artifactId>mybatis</artifactId> <version>x.x.x</version></dependency> 二、从 XML 中构建 SqlSessionFactory String r......

一个yuanbeth
16分钟前
0
0
聊聊spring cloud的LoadBalancerAutoConfiguration

序 本文主要研究一下spring cloud的LoadBalancerAutoConfiguration RibbonAutoConfiguration spring-cloud-netflix-ribbon-2.0.0.RC2-sources.jar!/org/springframework/cloud/netflix/ribb......

go4it
19分钟前
0
0
【转】使用Lombok来优雅的编码

前言 Lombok 是一种 Java™ 实用工具,可用来帮助开发人员消除 Java 的冗长,尤其是对于简单的 Java 对象(POJO)。它通过注解实现这一目的。 正文 添加依赖 在 pom.xml 文件中添加相关依赖:...

HAVENT
21分钟前
0
0
Dubbo 源码解读 —— 可支持序列化及自定义扩展

一、概述 从源码中,我们可以看出来。目前,Dubbo 内部提供了 5 种序列化的方式,分别为 fastjson、Hessian2、Kryo、fst 及 Java原生支持的方式 。 针对不同的序列化方式,对比内容如下: 名...

Ryan-瑞恩
28分钟前
0
0
MySQL内存设置—— MySQL server has gone away

set global max_allowed_packet=268435456

一梦心草
38分钟前
0
0
推导式

列表、集合和字典推导式 列表推导式是Python最受喜爱的特性之一。它允许用户方便的从一个集合过滤元素,形成列表,在传递参数的过程中还可以修改元素。形式如下: [expr for val in collect...

火力全開
43分钟前
0
0
maven配置文件settings.xml详解

settings.xml有什么用? 如果在Eclipse中使用过Maven插件,想必会有这个经验:配置settings.xml文件的路径。 settings.xml文件是干什么的,为什么要配置它呢? 从settings.xml的文件名就可以...

浮躁的码农
48分钟前
0
0
MakeCode图形化编程语言学习笔记:micro:bit编程练习题[图]

MakeCode图形化编程语言学习笔记:micro:bit编程练习题[图]: 基础训练题: Q1:摇晃micro:bit编程板,随机出现7个小动物图标中的一个,并且前后相邻两次出现的小动物不重复。 注:七个小动物...

原创小博客
48分钟前
0
0
Redis 压力测试说明

Redis 压力测试说明 redis压力测试 2014-03-24 21:41:07| 分类: 默认分类 | 标签:redis |举报|字号 订阅 这几天对比测试mongodb、redis、pg的性能,主要是在消息队列、消息处理、用户经纬度...

舒文joven
48分钟前
0
0
拉姆达表达式 追加 条件判断 Expression>

public static class PredicateBuilder {   /// <summary>   /// 机关函数应用True时:单个AND有效,多个AND有效;单个OR无效,多个OR无效;混应时写在AND后的OR有效   /// </summary...

Lytf
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部