倘若把前缀的定义改为包括末位,后缀的定义改为包括首位,探讨下面问题。
(这只是从一个角度思考,从别的角度思考,会有更多理解)
1.比如主串为:googoo.... 子串为googool
看主串,看到第7位如果不是l,于是你去研究刚刚我们想作为后缀的主串中的第二个goo改作为前缀行不行。这个做法是正确的。
2.但比如 主串为:aaaa…子串为aaaab
看主串,看到第四位如果不是b,你若像上题一样,去研究aaaa不作为后缀了,而是作为前缀行不行,这是多余的,因为前缀和后缀是一种情况。这导致不会像上题那样把子串往后移三位,而是移0位,没有进展。
从算法上来讲,你没有得到错误的结论,但是由于前后缀重合,你毫无进展,陷入了循环。
若按标准的定义,前缀后缀应为aaa。研究的过程就变成了把aaa(主串中后仨)作为后缀不行,又把这仨作为前缀,相当于舍弃了第一个a,往后串了1位,有进展。