模式串匹配---KMP
- 博客分类:
- 数据结构算法
朴素的的模式串匹配算法通常要在向前移动文本指针之后,回溯模式串指针,其效率为O(m*n),而KMP算法则挖掘了一些模式串中的一些信息,来加快匹配的效率。
KMP算法的紧随便是覆盖函数next。当模式串p[j]和文本串s[i]失配时,j指针不是简单的回溯,而是指向next[j]。
覆盖函数next如何定义呢,它本质上是找到即是模式串p的前缀,又是它的后缀的最长字符串,即找到最大的k使得p[0]p[1]....p[k-1]=p[j-k]p[j-k+1]..p[j-1],然后将next[j]赋值为k。当然,这样的赋值并非最优化,注意到如果p[j]=p[k],那next[j]和s[i]也必然失配,因此要递归的找到一个k使得p[j]!=p[k].
以下是KMP算法的代码:
#include<iostream>
using namespace std;
void get_nextval(char const* ptrn, int plen, int* nextval)
{
int i = 0;
nextval[i] = -1;
int j = -1;
while( i < plen-1 )
{
if( j == -1 || ptrn[i] == ptrn[j] ) //循环的if部分
{
++i;
++j;
if( ptrn[i] != ptrn[j] )
nextval[i] = j;
else
nextval[i] = nextval[j];
}
else //循环的else部分
j = nextval[j];
}
}
void get_next(char const* ptrn, int plen, int* nextval)
{
int i = 0;
nextval[i] = -1;
int j = -1;
while( i < plen-1 )
{
if( j == -1 || ptrn[i] == ptrn[j] ) //循环的if部分
{
++i;
++j;
nextval[i] = j;
}
else //循环的else部分
j = nextval[j]; //递推
}
}
int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)
{
int i = pos;
int j = 0;
while ( i < slen && j < plen )
{
if( j == -1 || src[i] == patn[j] )
{
++i;
++j; //匹配成功,就++,继续比较。
}
else
{
j = nextval[j];
}
}
if( j >= plen )
return i-plen;
else
return -1;
}
int main()
{
char p[9]={'a','b','a','a','b','c','a','b','a'};
int next[9];
get_nextval(p,9,next);
for(int i=0;i<9;++i)
cout<<next[i]<<" ";
cout<<endl;
}
发表评论
-
图的割点tarjan---zoj_1119
2011-10-24 23:00 1233http://acm.zju.edu.cn/on ... -
BFS与双向BFS---zoj_1505
2011-10-09 17:14 1643http://acm.zju.edu.c ... -
静态treap+线段树---zoj_2112
2011-09-29 23:06 1708http://acm.zju.edu ... -
NIM博弈游戏,SG函数---zoj_3084,zoj_2083
2011-09-23 23:00 1317Nim游戏是两个人进行的游戏有如下规则: ... -
多重背包--zoj_2156
2011-09-14 11:10 864首先介绍经典的三种背包问题,0-1背包,完全 ... -
八数码问题(A*&&双向BFS)---zoj_1217
2011-08-30 22:13 1665题目地址:http://acm.zju.edu.cn/onli ... -
ac自动机以及它上面的DFA
2011-08-08 23:04 2479AC自动机(Aho-Corasick)主要用 ... -
二分图最大匹配(匈牙利算法)--zoj1516,1525,2223
2011-07-20 22:36 1188二分图G(E,V)将点集合V分成两个部分L,R ... -
网络最大流(EK)---zoj_1734
2011-07-19 16:34 2132网络最大流是图论中的一个典型问题,为了精确的定 ... -
trie和前缀检查---zoj_2876
2011-07-13 23:03 869trie树是一种多叉树,广泛用于字典检索。如 ... -
位图bitmap
2011-07-13 21:08 916bitmap是一种广泛使用的数据结构,主要用在 ... -
LAC和RMQ的转化---zoj_3195
2011-07-12 22:35 1074我擦。。纠结了好久啊,从SF到TLE,先总结2 ... -
LAC的tarjan(离线)算法---zoj_1141
2011-07-08 17:52 1660LCA就不解释了,这里主要再次复习一下LC ... -
笛卡尔树以及treap---zoj_2243
2011-07-07 15:52 2841zoj_2243笛卡 ... -
线段染色,矩形切割,离散化---zoj_2301,zoj_1128
2011-06-24 22:32 1367染色问题:在一维坐标轴上(最右端为M),有N ... -
线段树---zoj_1610
2011-06-22 21:06 746线段树是一种二叉树的拓展,在线段树每个节点中 ... -
快速排序(qsort)
2011-06-16 17:03 779快速排序是一种高效的非稳定排序,它的基本思路 ... -
斐波那契散列
2011-06-16 16:38 3074斐波那契散列法其实是一种特殊的乘法散列,先来看乘法 ... -
强连通分支(scc)---tarjan
2011-06-15 16:17 1285本文大量 ... -
单源最短路径SPFA---zoj3146
2011-06-09 15:25 941针对Bellman-Ford算法效率比较低 ...
相关推荐
C#实现-模式串匹配-KMP,在朴素模式匹配的基础上,优化为C#版的KMP模式串匹配。
《数据结构》用C语言实现的模式匹配KMP算法,可用于求出子串在主串中的位置。
字符串处理- 单模式匹配- MP 算法与 KMP 算法.rar
kmp算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。next...
KMP 字符串模式匹配详解 KMP算法是对传统模式匹配算法的较大改进,在传统的模式匹配算法中,当出现主串中的字符与子串中的字符不等时,同时向前回溯了两个指针,一个是主串的指针,一个是子串的指针。而KMP算法的...
KMP字符串模式匹配算法ppt,KMP算法是很精妙的算法,同时比较难懂。KMP字符串模式匹配算法ppt
数据结构(C语言版)严蔚敏版,KMP算法演示示例ppt
字符串的模式匹配算法——KMP的C++实现。
字符串模式匹配KMP实验 字符串模式匹配KMP实验
代码封装了字符串的kmp模式匹配算法。kmp是一种非常快速的字符串匹配算法,效率比普通匹配算法高很多
串的模式匹配的C语言实现,同时,还会有完好的界面,使用户输入的数据KMP实现与传统实现两种结果进行对比,完全能通过。
KMP字符串模式匹配算法,内是ppt讲解,比较通俗易懂了。。
KMP字符串匹配算法,一种快速模式匹配算法
串匹配问题实际上就是一种模式匹配问题,即在给定的文本串中找出与模式串匹配的子串的起始位置。最基本的串匹配问题是关键词匹配(Keyword Matching)。所谓关键词匹配,是指给定一个长为n的文本串T[1,n]和长为m的...
《字符串模式匹配KMP算法》教学课例设计[归纳].pdf
实验二 串模式匹配算法(串实验) 实现功能:朴素的模式匹配算法(BF算法)、KMP改进算法(Next[ ])、KMP改进算法(NextVal[ ])。 主控菜单: 1.输入主串、子串和匹配起始位置 2.朴素的模式匹配算法 3.KMP改进算法...
关于KMP_字符串模式匹配算法的教学课件,详细讲解了Kmp 的原理与不足和改进
讲解完成了KMP模式匹配算法用于查找字符串
串匹配问题实际上就是一种模式匹配问题,即在给定的文本串中找出与模式串匹配的子串的起始位置。最基本的串匹配问题是关键词匹配(Keyword Matching)。所谓关键词匹配,是指给定一个长为n的文本串T[1,n]和长为m的...