麻烦解释下里面的前缀,后缀,真前缀,真后缀,和前缀函数!最好举个例子!

T="t1t2...tm"中的每一个ti都对应一个k得值,这个k值仅依赖于模式本身字符序列的构成,而与主串无关。用next[j]表示tj对应的k的值(1<<j<<m),则t1...tk-1即是t1...tj-1的真前缀,又是真后缀的最长子串,因此,将k=next[j]称为tj的前缀函数值。

天涯尽头无女友
浏览 121回答 1
1回答

一只萌萌小番薯

比如字符串S=aabaaaabaa是S的前缀,但只有a,aa,aab,aaba是它的真前缀真x缀就是不包含字符串自身的x缀前缀函数计算的是在模式匹配字符串里第n个字符匹配失败后,下一次可能匹配的最长移动距离,next[n]就是第n个字符所拥有的最长真后缀同时是该字符串前缀的串的长度,比如aabaaa -> 0 第一个字符始终为0aa -> 1aab -> 0aaba -> 1aabaa -> 2
打开App,查看更多内容
随时随地看视频慕课网APP