之前一篇KMP講的是直接的應(yīng)用，這一篇將借助兩道相似的POJ題目對(duì)next數(shù)組進(jìn)行深入一些的討論。
兩道題目分別是：
POJ 1961 2406，題意是給出一個(gè)串s，找出這個(gè)能表示成某個(gè)字串A的K次聯(lián)接，即s=[A...A] (K個(gè)A)，要求K最大，即A最小。
暴力可以過2406，但1961沒法過，超時(shí)。
看了discuss的討論，只要計(jì)算KMP算法中的next數(shù)組，判斷n (串長(zhǎng))能否被d = n-1-next[n-1] (即最后一個(gè)next)整除，若能，則s是s[next[n-1]...n-1]的n/d聯(lián)接。具體細(xì)節(jié)沒有證明。
下面給出我的一些想法，為什么以上判斷是正確的。
首先，若s可以表示成[A...A]，則next數(shù)組確實(shí)是符合以上整除的要求的，且從0到next[n-1]這個(gè)proper prefix (見上一篇KMP文章的定義)是s的最長(zhǎng)的proper suffix。
其次，為什么d整除n，就能斷定s是s[next[n-1]+1...n-1]的n/d次聯(lián)接呢？
1) 用文字表述太麻煩，用下圖說明
圖中顏色一致的段是一樣的（這是因?yàn)橄旅婺嵌问巧厦婺嵌蔚膒roper prefix），即上面的1等于下面的1，而由于下面的段是上面段的proper prefix，因此下面的1又等于上面的2，所以上面的1跟2是相等的。以此類推，上面的小段都是相等的。