KMP與最小覆寫子串
最小覆寫子串：對于某個字元串s，它的最小覆寫子串指的是長度最小的子串p，p滿足通過自身的多次連接配接得到q，最後能夠使s成為q的子串。
比如：
對于s="abcab"，它的最小覆寫子串p="abc"，因為p通過在它後面再接上一個p（即重疊0個字元），可以得到q="abcabc"，此時s是q的子串。
對于s="ababab"，它的最小覆寫子串為p="ab"。
根據KMP算法的next數組的定義，設字元串s的長度為n，則next[n] = next[n - 1]，n-1為s的最後一位。
next[n]表明s[0,1,2,...,next[n]-1] == s[n-next[n],...,n-1]，設這兩段分别為s1和s2。
若s1和s2的長度之和小于s的長度，則說明s1和s2分别為不重疊的字首和字尾，則最小覆寫子串必為s截去s2之後得到的字首。
若s1和s2的長度之和大于等于s的長度，則最小覆寫子串也必為s截去s2之後得到的字首。
以上兩種情況都可以推出這個結論：最小覆寫子串是s的字首，它的長度為n-next[n]。
我對KMP的一些了解（lyp點撥的）：pre[i]（或next[i]）的實質是串str[1..i]的最長且小于i的“相等前、字尾”分别為str[1..pre[i]]（字首）與str[(i-pre[i]+1)..i]（字尾），通俗講就是：使str[1..i]前k個字母與後k個字母相等的最大k值。
另外一個結論：
最小覆寫子串（串尾多一小段時，用字首覆寫）長度為n-next[n]（n-pre[n]），n為串長。
證明分兩部分：
１－長為n-next[n]的字首必為覆寫子串。
當next[n]<n-next[n]時，如圖a，長為next[n]的字首A與長為next[n]的字尾B相等，故長為n-next[n]的字首C必覆寫字尾B；
當next[n]>n-next[n]時，如圖b，将原串X向後移n-next[n]個機關得到Y串，根據next的定義，知長為next[n]的字尾串A與長為字首串B相等，X串中的長為n-next[n]的字首C與Y串中的字首D相等，而X串中的串E又與Y串中的D相等……可見X串中的長為n-next[n]的字首C可覆寫全串。
２－長為n-next[n]的字首是最短的。
如圖c，串A是長為n-next[n]的字首，串B是長為next[n]的字尾，假設存在長度小于n-next[n]的字首C能覆寫全串，則将原串X截去前面一段C，得到新串Ｙ，則Ｙ必與原串長度大于next[n]的字首相等，與next數組的定義（使str[1..i]前k個字母與後k個字母相等的最大k值。）沖突。得證！有人問，為什麼Ｙ與原串長大于next[n]的字首相等？由假設知原串的構成必為CCC……E（E為C的字首），串Ｙ的構成必為CC……E（比原串少一個Ｃ），懂了吧！
最後得出結論：總長度-next[n].
code：