前綴計演算法

1. 前綴函數

前綴 是指從串首開始到某個位置 結束的一個特殊子串。字元串 的以 結尾的前綴表示為
真前綴 指除了 本身的 的前綴。

後綴 是指從某個位置 開始到整個串末尾結束的一個特殊子串。字元串 的從 開頭的後綴表示為
真後綴 指除了 本身的 的後綴。

給定一個長度為 的字元串 ，其 前綴函數 定義為一個長度為 的數組 。其中 含義為：

對於字元串 和 ，若 對於所有 成立，則稱 是 的 周期 。

對於字元串 和 ，若 長度為 的前綴和長度為 的後綴相等，就稱 長度為 的前綴（後綴）是 的 border 。

【注】易知前綴函數 對應的就是字元串 的最長 border 的長度。

根據前綴函數的定義我們可以發現，相鄰的前綴函數值至多增加 1 ，故可以得到字元串 的前綴函數的計算公式：

【注】計算字元串的前綴函數的思想和 KMP 演算法中計算字元串失配數組的思想非常相似。

前綴函數可以用來實現 KMP 演算法，思路為：拼接模式串 和主串 ，得到 ， 為不在 和 中出現的字元。設 計算拼接後的字元串 的前綴函數，當出現 時，說明此時模式串匹配上了主串的子串 。

整個演算法時間復雜度為 。

根據上文中給出的性質，可以很容易求出字元串 的字元串周期 & border。假設 ，則可以在 時間內求出 的所有周期 & border。

給定字元串 ，其長度 ，計算 中不同的子串的數目。

【注】從頭部添加、頭部移除或尾部移除後計算不同子串的思想類似。

根據上文的性質可知，如果計算出 的前綴函數之後， 的最小周期為 。由字元串的周期的定義可知，最後字元串 刪去每段周期長度的字元串後，剩餘的最後一段字元串長度不一定是 。故如果 ，則 即是 的長度，否則不存在一個有效的壓縮，即 的長度為 。