下载此文档

算法导论之字符串匹配算法.pptx


文档分类:IT计算机 | 页数:约31页 举报非法文档有奖
1/31
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/31 下载此文档
文档列表 文档介绍
字符串匹配算法
我们经常要在一段文本中某个特定的位置找出某个特定的字符或模式。 由此,便产生了字符串的匹配问题。
假设文本是一个长度为n的数组T[1...n],模式是一个长度为m<=n的数组P[1....m]。
简单字符串匹配
目标是找出所有在文本T=abcabaabcaabac中的模式P=abaa所有出现。
该模式仅在文本中出现了一次,在位移s=3处。位移s=3是有效位移。
n = length(T) m = length(P)
int flag=1; for(s = 0 ; s < n-m ; s++)
{
flag=1;
for(i = 0 ; i < m ; i++)
{
if (P[i] != T[s+i]) {flag=0;break;}
}
if(flag) {cout << s; break;}
}
简单的字符串匹配算法用一个循环来找出所有有效位移,该循环对n-m+1个可能的每一个s值检查条件
P[0....m-1]=T[s....s+m-1]
简单字符串匹配算法,上图针对文本T=acaabc 和模式P=aab。
n-m+1个可能的位移s中的每一个值,比较相应的字符的循环。
所以,在最坏情况下,此简单模式匹配算法的运行时间为O((n-m+1)m)。
对于目的字串T是banananobano,要匹配的字串P是nano的情况
只要P字串第一个字符先和T字串的第一个字符比较,如果相同就比较下一个,如果不同就把P右移一下,之后再从P的每一个字符比较,这个算法的运行过程如下图。
nano
时间复杂度是O(m * n)
KMP算法

算法导论之字符串匹配算法 来自淘豆网m.daumloan.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数31
  • 收藏数0 收藏
  • 顶次数0
  • 上传人h377683120
  • 文件大小444 KB
  • 时间2018-07-26
最近更新