題意：字符串s可以被分割為，其中，求整個字符串及其子串中有多少種字符串可以被這樣分割

暴力做法：

先考慮暴力做法，記??表示??與??的最長公共前綴，那么類似于??可以得到轉(zhuǎn)移方程 ，那么如果，那么就說明以??到??這一段的字符串在??之后又再次出現(xiàn)了，那么我們就可以得到上圖中最前面的藍色兩部分，特別的，在上圖中可以發(fā)現(xiàn)，之后出現(xiàn)的藍色與橙色在之后重復(fù)出現(xiàn)，那么我們可以在??之后枚舉（因為這樣才找到了前面的兩個藍色部分），同樣類似于之前的，如果有?（只要比藍色部分多就行了）?那么藍色和橙色部分也重復(fù)出現(xiàn)，但是綠色部分的長度至少為1，所以??從??開始枚舉，同時?，那么答案就要加上，本著交一發(fā)試試的心態(tài)，然后不出意外就TLE了

優(yōu)化：

????可以發(fā)現(xiàn)，求??的過程其實沒辦法去優(yōu)化的，同時??和??也沒辦法優(yōu)化，因為我們總是需要枚舉兩個點去找到藍色部分，那么我們可以嘗試優(yōu)化?，對于??， 若存在??對答案有貢獻，那么?最少也是 （+1是因為要有一個綠色部分），也就是說，從?后面的第?個字符開始到整個字符串末尾都有可能對答案產(chǎn)生貢獻。

????記表示從開始長度為 ?的貢獻，若?，那么根據(jù)上面的分析，，都需要加一，顯然這個是個差分然后求前綴和的過程。那么現(xiàn)在就可以枚舉和來計算貢獻了，根據(jù)暴力解法，我們應(yīng)該從開始長度為一直加到長度為這一段的值，也就是，那么這又是一個前綴和的過程，為了方便，我們可以把數(shù)組定義為差分數(shù)組，然后求兩次前綴和就可以了

按理說應(yīng)該是能過得，但是

那么就是一些小細節(jié)可以優(yōu)化了，對于滿足條件的貢獻至多不超過原字符串長度的一半，因此第二維開到一半就夠了。