软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 编程语言 -> KMP算法详解 -> 正文阅读

[编程语言]KMP算法详解


这几天学习kmp算法,解决字符串的匹配问题,开始的时候都是用到BF算法,(BF(Brute Force)算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。BF算法是一种蛮力算法。)虽然也能解决一些问题,但是这是常规思路,在内存大,数据量小,时间长的情况下,还能解决一些问题,但是如果遇到一些限制时间和内存的字符串问题,肯定会超时,这是我们就想到了kmp算法,(KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特--莫里斯--普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。)kmp算法的难点是kmp中的next数组的了解和求法。上网查了很多资料,发现参差不齐,研究了很久,才觉得豁然开朗,,借鉴网上资源以及自己的了解,现总结如下,存在很多不足之处,希望大家能批评指正!!
一、模拟字符串比较过程如下:
         1.
[img]http://image.beekka.com/blog/201305/bg2013050103.png
首先,字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。
2.
[img]http://image.beekka.com/blog/201305/bg2013050104.png
因为B与A不匹配,搜索词再往后移。
3.
[img]http://image.beekka.com/blog/201305/bg2013050105.png
就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。
4.
[img]http://image.beekka.com/blog/201305/bg2013050106.png
接着比较字符串和搜索词的下一个字符,还是相同。
5.
[img]http://image.beekka.com/blog/201305/bg2013050107.png
直到字符串有一个字符,与搜索词对应的字符不相同为止。
6.
[img]http://image.beekka.com/blog/201305/bg2013050108.png
这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把"搜索位置"移到已经比较过的位置,重比一遍。
7.
[img]http://image.beekka.com/blog/201305/bg2013050107.png
一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。
8.
[img]http://image.beekka.com/blog/201305/bg2013050109.png
怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。
9.
[img]http://image.beekka.com/blog/201305/bg2013050107.png
已知空格与D不匹配时,前面六个字符"ABCDAB"是匹配的。查表可知,最后一个匹配字符B对应的"部分匹配值"为2,因此按照下面的公式算出向后移动的位数:

  移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4,所以将搜索词向后移动4位。
10.
[img]http://image.beekka.com/blog/201305/bg2013050110.png
因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2("AB"),对应的"部分匹配值"为0。所以,移动位数 = 2 - 0,结果为 2,于是将搜索词向后移2位。
11.
[img]http://image.beekka.com/blog/201305/bg2013050111.png
因为空格与A不匹配,继续后移一位。
12.
[img]http://image.beekka.com/blog/201305/bg2013050112.png
逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 - 2,继续将搜索词向后移动4位。
13.
[img]http://image.beekka.com/blog/201305/bg2013050113.png
逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 - 0,再将搜索词向后移动7位,这里就不再重复了。
14.
[img]http://image.beekka.com/blog/201305/bg2013050114.png
下面介绍《部分匹配表》是如何产生的。
首先,要了解两个概念:"前缀"和"后缀"。 "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。
15.
[img]http://image.beekka.com/blog/201305/bg2013050109.png
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例,

  - "A"的前缀和后缀都为空集,共有元素的长度为0;
  - "AB"的前缀为[A],后缀为[B],共有元素的长度为0;
  - "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;
  - "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;
  - "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为1;
  - "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为2;
  - "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

16.
[img]http://image.beekka.com/blog/201305/bg2013050112.png
"部分匹配"的实质是,有时候,字符串头部和尾部会有重复。比如,"ABCDAB"之中有两个"AB",那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候,第一个"AB"向后移动4位(字符串长度-部分匹配值),就可以来到第二个"AB"的位置。
二、next数组实现的代码:
代码:
<span style="font-size:18px;">void makeNext(const char P[],int next[])
{
    int q,k;//q:模版字符串下标;k:最大前后缀长度
    int m = strlen(P);//模版字符串长度
    next[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0
    for (q = 1,k = 0; q < m; ++q)//for循环,从第二个字符开始,依次计算每一个字符对应的next值
    {
        while(k > 0 && P[q] != P[k])//递归的求出P[0]···P[q]的最大的相同的前后缀长度k
            k = next[k-1];          //不理解没关系看下面的分析,这个while循环是整段代码的精髓所在,确实不好理解  
        if (P[q] == P[k])//如果相等,那么最大相同前后缀长度加1
        {
            k++;
        }
        next[q] = k;
    }
}</span>

 现在我着重讲解一下while循环所做的工作:
  1.   已知前一步计算时最大相同的前后缀长度为k(k>0),即P[0]···P[k-1];
  2.   此时比较第k项P[k]与P[q],如图1所示
  3.   如果P[K]等于P[q],那么很简单跳出while循环;
  4.   关键!关键有木有!关键如果不等呢???那么我们应该利用已经得到的next[0]···next[k-1]来求P[0]···P[k-1]这个子串中最大相同前后缀可能有同学要问了——为什么要求P[0]···P[k-1]的最大相同前后缀呢???是啊!为什么呢? 原因在于P[k]已经和P[q]失配了,而且P[q-k] ··· P[q-1]又与P[0] ···P[k-1]相同,看来P[0]···P[k-1]这么长的子串是用不了了,那么我要找个同样也是P[0]打头、P[k-1]结尾的子串即P[0]···P[j-1](j==next[k-1]),看看它的下一项P[j]是否能和P[q]匹配。如图2所示

 
 [img]http://images.cnitblog.com/blog/432480/201307/30163843-2fd01a5b306b4fbb8183b0a7c145d79c.png[img]http://images.cnitblog.com/blog/432480/201307/30171002-e67282f4d1d84cb59e0152826b58e6ac.png
三、next数组的优化代码:
<span style="font-size:18px;">void get_next()
{
	int i=0,j=-1;
	next[0]=-1;
	while(i<len2)
	{
		if(j==-1||s2[i]==s2[j])
		{
			i++;
			j++;
			next[i]=j;
		}
		else
		{
			j=next[j];
		}	
	}	
} </span>

附件:kmp算法完整代码:

<span style="font-size:18px;">#include<stdio.h>
#include<string.h>
#define N 100005
char s[2*N];
char s1[N];
char s2[N];
int next[N];
int len1,len2,len;
void get_next()
{
	int i=0,j=-1;
	next[0]=-1;
	while(i<len2)
	{
		if(j==-1||s2[i]==s2[j])
		{
			i++;
			j++;
			next[i]=j;
		}
		else
		{
			j=next[j];
		}	
	}	
} 
void KMP()
{
	int i=0;
	int j=0;
	get_next();	
	while(i<len&&j<len2)
	{
		if(j==-1||s[i]==s2[j])
		{
			i++;
			j++;
		}
		else
		{
			j=next[j];
		}
	}
	if(j==len2)
	{
		printf("yes\n");
		return ;
	}
	else
	{
		printf("no\n");
		return ;
	}
}
int main(void)
{
	while(scanf("%s%s",s1,s2)!=EOF)
	{
		len1=strlen(s1);
		len2=strlen(s2);
		if(len1<len2)
		{
			printf("no\n");
			continue;
		}
		strcpy(s,s1);
		strcat(s,s1);
		len=2*len1;
		memset(next,-1,sizeof(next));
		KMP();
	}
	return 0;
}</span>


......显示全文...
    点击查看全文


上一篇文章      下一篇文章      查看所有文章
2016-04-02 20:55:35  
编程语言 最新文章
Java面试题(1)
ReactiveX序列——RxSwift
C++STL之ACM相关知识大全
c++中vector向量几种情况的总结(向量指针,
SSH框架整合demo
JAX
UVA
curl备忘(1)
C#机房重构——万事开头难(二)
OJ刷题
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年1日历
2018-1-16 17:21:11
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --