首页 > 其他 > 详细

字符串前缀,真前缀,后缀,真后缀,及前缀函数

时间:2014-05-18 18:27:48      阅读:1640      评论:0      收藏:0      [点我收藏+]

举个例子,如字符串 ababc

首先,不考虑空字符,所有的前缀有a, ab, aba, abab, ababc,其中真前缀有a, ab, aba, abab

同理可以理解后缀,真前(后)缀就是指不包含自身的前(后)缀

前缀函数next[j]是指某个字符串的最长真后缀同时也是它的前缀的子串长度。不太理解可以看下面的例子

a -> 0

ab -> 0

aba -> 1

abab -> 2

ababc -> 0

前缀函数在字符串的匹配中用的较多,如KMP等。它主要是表明在一次匹配失败后模式串可以往后移动的最大步长。


字符串前缀,真前缀,后缀,真后缀,及前缀函数,布布扣,bubuko.com

字符串前缀,真前缀,后缀,真后缀,及前缀函数

原文:http://blog.csdn.net/daydayyup/article/details/26099107

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!