首页 > 代码库 > 字符串前缀,真前缀,后缀,真后缀,及前缀函数

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

举个例子,如字符串 ababc

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

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

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

a -> 0

ab -> 0

aba -> 1

abab -> 2

ababc -> 0

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