KMP

原创
2019/11/16 23:53
阅读数 61

字符串匹配算法 

针对被匹配字段生产一个部分匹配表  

A B C D A B D 

0 0 0  0 1  2 0     部分匹配表 

熟悉前缀与后缀的概念 ,“部分匹配表” 的生产就是根据前缀、后缀的最苍的共有元素的长度 

前缀:除去最后一个字符外,一个字符串的全部头部组合【{A},{AB},{ABC},{ABCD},{ABCDA},{ABCDAB}】

后缀: 除了第一个字符串外。一个字符串的全部尾部组合 【{D},{BD},{ABD},{}】

我们会针对A B C D A B D 中 {A,AB,ABC,ABCD,ABCDA,ABCDAB,ABCDABD}以前进行前前后缀的处理,然后比对前后缀中 ,相同的字符 ,并在对应的位置标记相同的个数,形成部分匹配表 

 

 

 

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部