- 1、本文档共43页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第4章串资料
讨论一般情况。 主串S为 ‘s1s2 … si -1si …sn’, 模式串T为‘p1p2… pj -1pj … pm’ 当si !=pj时, si应与T中哪个字符再比较? 假设应与pk继续比较,则模式中前k – 1 个字符的子串必须满足下列关系式 ‘p1p2…pk-1 ’= ‘si-k+1si-k+2……si-1 ’ (4-2) 而已经得到的“部分匹配”的结果是 ‘pj-k+1pj-k+2……pj-1 ’= ‘si-k+1si-k+2……si-1 ’ (4-3) 由(4-2)和(4-3)推得下列等式 ‘p1p2…pk-1 ’ = ‘pj-k+1pj-k+2……pj-1 ’ (4-4) 匹配仅需从模式中第k个字符与主串中第i个字符比较起继续进行。 设next[j] = k,由此可引出模式串的next函数的定义: 0 当j = 1 时 next[j] = Max {k | 1 k j 且‘P1…Pk-1’= ‘Pj-k+1…Pj-1’} 当此集合不空时 1 其它情况 由此定义可推出下列模式串的next函数值: j 1 2 3 4 5 6 7 8 模式串 a b a a b c a c next[j] 0 1 1 2 2 3 1 2 int Index_KMP (SString S, SString T, int pos ) { i = pos ; j = 1 ; while ( i = S [ 0 ] j = T[ 0 ] ) { if ( j = = 0 || S[ i ] = = T[ j ] ) { ++ i ; ++ j ; } // 继续比较后续字符 else j = next [ j ] ; // 模式串向右移动 } if ( j T[ 0 ] ) return i – T [ 0 ] ; // 匹配成功 else return 0 ; } // Index_KMP 怎么求next数组的值?用递推的方法:归纳法 设next(1) = 0,设next(j) = k,欲求得next[j+1]。 (1)如果Pk = Pj,显然next[j+1] = k+1。 (2)如果Pk ≠ Pj,则 ‘p1p2…pk ’ ≠ ‘pj-k+1pj-k+2……pj ’ ,这就可以看成是一个模式匹配问题,主串和模式串是同一个串。于是寻找k’, 若next[k]=k’,使得‘p1p2…pk’’ =‘pj-k’+1pj-k’+2……pj ’ ,则next[j+1]=next[k]+1。如果等式不成立,则继续找下一个k’,这是个迭代的过程。 (3)如果不存这样的k’,说明P0 P1……Pj中没有前后相等的子串,因此next[j+1] =1。 仿照KMP算法,可得到求next函数值的算法。 void get_next ( SString T , int next[] ) { // 求模式串T的next函数值并存入数组next。 i = 1 ; next [ 1 ] = 0 ; j = 0 ; while ( i T [ 0 ] ) { if ( j = = 0 || T [ i ] = = T[j] ) { ++ i ; ++ j ; next[i] = j ; } else j = next[j] ; }//while } // get_next 说明: 1)算法4.5在一般情况下,其实际的执行时间近似于O(n+m),至今仍被采用。 2)KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才显得比算法4.5快的多。 3)KMP算法的最大特点是指示主串的指针不需回溯,对主串仅需
您可能关注的文档
最近下载
- 优质工程创优监理方案.pdf
- 第1-4单元期中重难点检测(试题)-2024-2025学年数学三年级上册北师大版.docx VIP
- 大疆 精灵 Phantom 4 Pro V2.0 快速入门指南 用户手册.pdf
- XX省传染病监测预警与应急指挥信息平台项目监测预警信息平台采购需求.docx VIP
- 最满意的三项工作和最不满意的一项工作3篇.docx
- 第1-4单元期中重难点卷(试题)-2024-2025学年数学三年级上册北师大版.docx VIP
- 送阅件-兖矿集团审计风险部.PDF
- 公司人力资源管理诊断报告.pptx
- NB∕T 31021-2012 风力发电企业科技文件归档与整理规范.pdf
- 辽宁省名校联盟 2024年高三 10 月份联合考试 物理试卷(含答案解析).pdf
文档评论(0)