- 浏览: 2962838 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (2529)
- finance (1459)
- technology (218)
- life (343)
- play (150)
- technology-component (0)
- idea (6)
- house (74)
- health (75)
- work (32)
- joke (23)
- blog (1)
- amazing (13)
- important (22)
- study (13)
- Alternative (0)
- funny (8)
- stock_technology (12)
- business (16)
- car (21)
- decorate (4)
- basketball (2)
- English (16)
- banker (1)
- TheBest (1)
- sample (2)
- love (13)
- management (4)
最新评论
-
zhongmin2012:
BSM确实需要实践,标准ITIL服务流程支持,要做好,需要花费 ...
BSM实施之前做什么 -
shw340518:
提示楼主,有时间逻辑bug:是你妈二十那年写的 那会儿连你爹都 ...
80后辣妈给未来儿子的信~我的儿,你也给我记住了~~~ -
guoapeng:
有相关的文档吗?
it项目管理表格(包含146个DOC文档模板) -
solomon:
看到的都是 这种 CTRL+C 和 CTRL+V 的文章, ...
Designing a website with InfoGlue components -
wendal:
恩, 不错. 有参考价值
Designing a website with InfoGlue components
串行串匹配算法
KMP算法
KMP算法的关键是根据给定的模式串W[1,m],定义一个next函数。next函数包含了模式串本身局部匹配的信息。next函数的定义如下:
KMP算法的基本思想是:假设在模式匹配的进程中,执行T[i]和W[j]的匹配检查。若T[i]=W[j],则继续检查T[i+1]和
W[j+1]是否匹配。若T[i]<>W[j],则分成两种情况:若j=1,则模式串右移一位,检查T[i+1]和W[1]是否匹配;若1&
lt;j<=m,则模式串右移j-next(j)位,检查T[i]和W[next(j)]是否匹配。重复此过程直到j=m或i=n结束。
kmp算法
[编辑本段
]
kmp算法-概述
一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。
[编辑本段
]
kmp算法-学习介绍
完全掌握KMP算法思想
学过数据结构的人,都对KMP算法印象颇深。尤其是新手,更是难以理解其涵义,搞得一头雾水。今天我们就来面对它,不将它彻底搞懂,誓不罢休。
如今,大伙基本上都用严蔚敏老师的书,那我就以此来讲解KMP算法。(小弟正在备战考研,为了节省时间,很多课本上的话我都在此省略了,以后一定补上。)
严老的《数据结构》79页讲了基本的匹配方法,这是基础。先把这个搞懂了。
80页在讲KMP算法的开始先举了个例子,让我们对KMP的基本思想有了最初的认识。目的在于指出“由此,在整个匹配的过程中,i指针没有回溯,”。
我们继续往下看:
现在讨论一般情况。
假设 主串:s: ‘s(1) s(2) s(3) ……s(n)’ ; 模式串 :p: ‘p(1) p(2) p(3)…..p(m)’
把课本上的这一段看完后,继续
现在我们假设 主串第i个字符与模式串的第j(j<=m)个字符‘失配’后,主串第i个字符与模式串的第k(k<j)个字符继续比较
此时,s(i)≠p(j), 有
主串: S(1)…… s(i-j+1)…… s(i-1) s(i) ………….
|| (相配) || ≠(失配)
匹配串: P(1) ……. p(j-1) p(j)
由此,我们得到关系式
‘p(1) p(2) p(3)…..p(j-1)’ = ’ s(i-j+1)……s(i-1)’
由于s(i)≠p(j),接下来s(i)将与p(k)继续比较,则模式串中的前(k-1)个字符的子串必须满足下列关系式,并且不可能存在 k’>k 满足下列关系式:(k<j),
‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(i-k+1)s(i-k+2)……s(i-1)’
即:
主串: S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) ………….
|| (相配) || || ?(有待比较)
匹配串: P(1) p(2) …… p(k-1) p(k)
现在我们把前面总结的关系综合一下
有:
S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) ……
|| (相配) || || || ≠(失配)
P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j)
|| (相配) || || ?(有待比较)
P(1) p(2) ……. p(k-1) p(k)
由上,我们得到关系:
‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(j-k+1)s(j-k+2)……s(j-1)’
接下来看“反之,若模式串中存在满足式(4-4)。。。。。。。”这一段。看完这一段,如果下面的看不懂就不要看了。直接去看那个next函数的源程序。(伪代码)
K 是和next有关系的,不过在最初看的时候,你不要太追究k到底是多少,至于next值是怎么求出来的,我教你怎么学会。
课本83页不是有个例子吗?就是 图4.6
你照着源程序,看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。
然后找几道练习题好好练练,一定要做熟练了。现在你的脑子里已经有那个next算法的初步思想了,再回去看它是怎么推出来的,如果还看不懂,就继续做练习,做完练习再看。相信自己!!!
附:
KMP算法查找串S中含串P的个数count
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
inline void NEXT(const string& T,vector<int>& next)
{
//按模式串生成vector,next(T.size())
next[0]=-1;
for(int i=1;i<T.size();i++ ){
int j=next[i-1];
while(T!=T[j+1]&& j>=0 )
j=next[j] ; //递推计算
if(T==T[j+1])next=j+1;
else next=0; //
}
}
inline string::size_type COUNT_KMP(const string& S,
const string& T)
{
//利用模式串T的next函数求T在主串S中的个数count的KMP算法
//其中T非空,
vector<int> next(T.size());
NEXT(T,next);
string::size_type index,count=0;
for(index=0;index<S.size();++index){
int pos=0;
string::size_type iter=index;
while(pos<T.size() && iter<S.size()){
if(S[iter]==T[pos]){
++iter;++pos;
}
else{
if(pos==0)++iter;
else pos=next[pos-1]+1;
}
}//while end
if(pos==T.size()&&(iter-index)==T.size())++count;
} //for end
return count;
}
int main(int argc, char *argv[])
{
string S="abaabcacabaabcacabaabcacabaabcacabaabcac";
string T="ab";
string::size_type count=COUNT_KMP(S,T);
cout<<count<<endl;
system("PAUSE");
return 0;
}
补上个Pascal的KMP算法源码
PROGRAM Impl_KMP;
USES
CRT;
CONST
MAX_STRLEN = 255;
VAR
next : array [ 1 .. MAX_STRLEN ] of integer;
str_s, str_t : string;
int_i : integer;
Procedure get_nexst( t : string );
Var
j, k : integer;
Begin
j := 1; k := 0;
while j < Length(t) do
begin
if ( k = 0 ) or ( t[j] = t[k] ) then
begin
j := j + 1; k := k + 1;
next[j] := k;
end
else k := next[k];
end;
End;
Function index( s : string; t : string ) : integer;
Var
i, j : integer;
Begin
get_next(t);
index := 0;
i := 1; j := 1;
while ( i <= Length(s) ) and ( j <= Length(t) ) do
begin
if ( j = 0 ) or ( s[i] = t[j] ) then
begin
i := i + 1; j := j + 1;
end
else j := next[j];
if j > Length(t) then index := i - Length(t);
end;
End;
BEGIN
ClrScr;{清屏,可不要}
Write(‘s = ’);
Readln(str_s);
Write(‘t = ’);
Readln(str_t);
int_i := index( str_s, str_t );
if int_i <> 0 then
begin
Writeln( 'Found' , str_t,' in ', str_s, 'at ', int_i,' .' );
end
else
Writeln( 'Cannot find ', str_t,' in' , str_s, '. ');
END.
index函数用于模式匹配,t是模式串,s是原串。返回模式串的位置,找不到则返回0
发表评论
-
New Enterprise Security Solutions
2011-09-13 15:46 0<!-- [if !mso]> <styl ... -
ES Announces Enterprise Security Solutions
2011-09-13 15:40 0<!-- [if !mso]> <styl ... -
linux下如何将文件打包、压缩并分割成制定大小?
2010-09-15 18:52 3318将大文件或目录打包、 ... -
rhel4 yum安装, 使用
2010-09-07 16:37 0第一种方法: yum源来自chinalinuxpub.com ... -
Windows: 远程自动安装程序
2010-08-26 15:48 1107问题的提出 作为 ... -
Oracle体系结构
2010-08-07 09:53 1044Oracle体系结构 Oracle Server包括Oracl ... -
ocp sesson 3
2010-07-31 14:39 0show parameter undo 只有 默认情况下服务 ... -
ocp session 2
2010-07-25 17:00 0/home/oracle/raInventory/orains ... -
ocp session 1
2010-07-24 13:02 0ocp first lesson D:\oracle_cou ... -
Python的xmlrpc调试
2010-07-19 23:55 2132Python的xmlrpc 调 试 ----------- ... -
mdadm使用详解及RAID 5简单分析
2010-07-11 16:19 1399http://blog.csdn.net/chinalinux ... -
Linux的lvm的基本配置步骤
2010-07-11 14:53 12901.增加硬件 增加的ide硬盘前缀为hd,scs ... -
OCP study material
2010-07-11 13:52 0\\192.168.1.105watch -n 1 'stat ... -
apache+python+mod_python+django 编译安装指南
2010-06-24 17:25 14771、本文将知道你在 linux 下使用源码包安装 ... -
在ubuntu下配置apache运行python脚本
2010-06-22 16:11 2279常用的简单命令 sudo apt ... -
Python 2.5 Quick Reference
2010-06-21 11:18 1473... -
shell 面试题汇集
2010-06-10 19:50 1066利用 top 取某个进程的 CPU 的脚本 : ... -
shell程序面试题
2010-06-10 19:48 29321.要求分析Apache访问日志,找出里面数量在前面100位的 ... -
EMC技术支持工程师笔试部分试题回忆
2010-06-07 15:16 1655要查看更多EMC公司笔经相关信息,请访问EMC公司校园招聘CL ... -
linux shell 条件语句
2010-06-03 23:29 1799...
相关推荐
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
KMP算法,全称为Knuth-Morris-Pratt算法,是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Morris和Robert Pratt三位学者提出。它的主要目标是在一个长字符串(主串A)中查找是否存在一个指定的短字符串(模式...
### 数据结果 KMP算法实验报告 #### 实验背景与目的 本实验主要针对《数据结构》课程中的字符串处理部分,具体涉及的是模式匹配算法——KMP算法。通过实验加深学生对串类型及其基本操作的理解,并重点掌握两种重要...
KMP算法,全称为Knuth-Morris-Pratt算法,是一种在字符串中寻找子串的高效搜索算法。它由D.E. Knuth、V. Morris和J.H. Pratt三位学者于1970年提出,主要用于解决模式匹配问题。传统的KMP算法避免了不必要的字符比较...
KMP算法是一种改进的字符串匹配算法,由Donald Knuth、Morris和Frank Pratt共同提出,其主要特点是在匹配过程中能够避免不必要的字符比较,从而提高搜索效率。 KMP算法的核心思想是构建一个部分匹配表(也称为失败...
`KMP算法.cpp`文件应该包含了这些实现逻辑,通过编译生成的`KMP算法.exe`可执行文件可以直接运行并测试。 4. **性能分析** KMP算法的时间复杂度为O(n + m),其中n为主串长度,m为子串长度。这是因为即使最坏情况下...
**KMP算法实现模板(C++版) ACM算法** KMP(Knuth-Morris-Pratt)算法是一种在文本字符串中查找子串匹配的有效方法,尤其适用于已经预处理了模式串(子串)的匹配信息。它是由D.E. Knuth、V. Morris和J.H. Pratt...
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
"模式匹配的KMP算法" 模式匹配的KMP算法是计算机科学领域中的一种经典算法,用于解决串的模式匹配问题。该算法可以高效地查找目标串中是否包含某个模式串,并返回模式串在目标串中的起始位置。 模式匹配的KMP算法...
《字符串模式匹配KMP算法》教学课例设计 在这篇教学设计中,我们旨在帮助学生掌握KMP字符串模式匹配算法的基本概念和应用。通过本课例设计,学生将了解KMP算法的应用普遍性、实现机制和时间复杂度,并掌握计算next...
数据结构中的KMP算法是一种高效的字符串匹配算法,由D.E.Knuth、V.J.Morris和J.H.Pratt三位学者提出,因此得名KMP(Knuth-Morris-Pratt)。该算法主要用于在一个文本串中查找一个模式串(即目标字符串)是否存在。...
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法
BF 算法和 KMP 算法在字符串匹配中的应用 BF 算法和 KMP 算法是两种常用的字符串匹配算法,分别应用于不同的场景中。本文将对这两种算法进行详细的分析和比较,以便更好地理解它们的原理和应用。 BF 算法 BF ...
模式匹配中的KMP算法的实现 模式匹配是计算机科学领域中的一个研究热点,串的模式匹配算法是其中的一个重要分支。在模式匹配中,KMP算法是一个非常重要的算法,它可以高效地实现串的模式匹配。下面我们将详细介绍...
### 字符串KMP算法C语言实现解析 在计算机科学领域,字符串匹配是常见的操作之一,其中KMP算法(Knuth-Morris-Pratt算法)因其高效性而被广泛使用。KMP算法由Donald Knuth、James H.Morris以及Vaughan Pratt共同...
KMP算法,全称Knuth-Morris-Pratt算法,是一种高效的字符串匹配算法,由Donald Knuth、James H. Morris和 Vaughan Pratt三位学者在1970年提出。该算法主要用于解决在一个大文本串(A)中查找是否存在一个指定的小...
数据结构中KMP算法过程的Flash演示
在数据结构和算法的学习中,理解并掌握KMP算法对于解决字符串匹配问题至关重要。 KMP算法的核心是构建一个“部分匹配表”(也称为“失败指针”或“前缀函数”),它记录了子字符串的每一个前缀和后缀的最大公共长度...
kmp算法 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串...