Count Substrings

C(n,2) + n + 1，分別統計長度大於一、等於一、等於零的子字串。時間複雜度O(1)。

Count Distinct Substrings

利用LCP Array，時間複雜度O(N)。

int sum = 0; for (int i=0; i<n; i++) sum += n - sa[i] - lcpa[i];

演算法（Karp–Miller–Rosenberg Algorithm）

統計每個子字串的出現次數、出現位置。

其實就是Prefix-Doubling Algorithm的延伸版本。依序排序長度為一、二、四、八、……的子字串，把每次排序的名次統統記錄下來。然後利用名次，統計長度為一、二、四、八、……的子字串的出現次數、出現位置。總時間複雜度仍是O(NlogN)。

length = 1                   length = 2
       | 0 1 2 3 4 5 6 7            | 0 1 2 3 4 5 6 7
s      | a b a a b b a a     s      | a b a a b b a a
rank   | 0 1 0 0 1 1 0 0     rank   | 1 3 0 1 4 3 0 2
repeat | 5 3 5 5 3 3 5 5     repeat | 2 2 2 2 2 2 2 1 

a      | 0 2 3 6 7           aa     | 2 6
b      | 1 4 5               ab     | 0 3
                             ba     | 1 5
                             bb     | 4
                             a      | 7

要尋找長度不是一、二、四、八、……的子字串出現位置，一樣也是使用排序，找出名次，再統計出現位置。排序時，利用長度最接近、略短於目前長度的子字串排序結果，一樣也是先比前半段，再比後半段，前後兩段會重疊。時間複雜度也是O(N)。

Longest Repeated Substring

「最長重覆子字串」是重複出現兩次以上的子字串當中，其長度最長者。可能有許多個。

子字串重複出現有三種定義：位置可以重疊、位置不得重疊、位置必須連續。

abababaxaba

可以重疊的 Longest Repeated Substring 就是 ababa
不得重疊的 Longest Repeated Substring 就是 aba
必須連續的 Longest Repeated Substring 就是 ab 和 ba

最佳化的對象，也有三種類型：週期最長的、綿延最長的，次數最多的。

abcdabcdijkijkijkzzzzz

以必須連續重複出現的子字串為例
週期最長的 abcd
綿延最長的 ijk
次數最多的 z

名詞整理：

square = 連著出現剛好兩次的substring
cube = 連著出現剛好三次的substring
repetition = 連著出現兩次以上的substring
period = 此substring連著出現，形成原字串
factor = 1. substring / 2. period
tandem repeat (生物學用詞) = repetition
repeated substring = 出現兩次以上的substring，通常可以重疊。
consecutive repeated substring (非正式用法) = repetition

可以重疊的Longest Repeated Substring

LCP Array的最大值就是答案。各位用力想吧！時間複雜度O(N)。

ICPC 3901 4513

不得重疊的Longest Repeated Substring

試誤法，以Binary Search找出最長重複子字串的長度。

看看後綴陣列是否有一段連續區間的LCP長度，恰好是最長重複子字串的長度，並且區間要足夠寬，讓子字串不重疊。

時間複雜度O(NlogN)。

必須連續的Longest Repeated Substring
Longest Tandem Repeat

接連出現兩次以上的子字串，其長度最長者。可能有許多個。

與前者一樣，時間複雜度O(NlogN)。也有O(N)的演算法：http://csiflabs.cs.ucdavis.edu/~gusfield/lineartime.pdf。

Periodic String【尚無正式名稱】

判斷一個字串，是不是一個子字串連續重複數次所形成的。找出這個子字串。

KMP Algorithm、Gusfield's Algorithm、LCP Array都可以用來解決這個問題。此處介紹LCP Array的解法。

窮舉週期長度k，看看第0個後綴、第k-1個後綴的LCP長度是不是等於n-k。時間複雜度O(N)。

UVa 455 10298

Most Consecutive Repeated Substring【尚無正式名稱】

「最多連續重覆子字串」是重複出現最多次的子字串。可能有許多個，當中一定會有位置不重疊的。

窮舉週期。針對每種週期，以週期長度L將字串切成小段。週期為L的「最多連續重複子字串」，一定會在s[L⋅i]和s[L⋅(i+1)]重複出現相同字元。窮舉每種i，求s[L⋅i]和s[L⋅(i+1)]的LCP長度，往前、往後都求，接著計算重複出現次數，取最大者。

由於有大量的LCP需要計算，可以使用Range Minimum Query來查詢LCP Array的區間最小值。如果將RMQ轉換成±1 RMQ，時間複雜度可達O(1)。

時間複雜度O(N/1) + O(N/2) + ... + O(N/N) = O(NlogN)。

切成小段，也許可以改成LZ-index。

UVa 10829

Shortest Unique Substring

「最短唯一子字串」是只有出現一次的子字串當中，其長度最短者。可能有許多個。

Minimal Unique Substring與Maximal Repeated Substring

「極小唯一子字串」是局部極值，「最短唯一子字串」是全域極值，最短的「極小唯一子字串」就是「最短唯一子字串」。「極大重複子字串」與「最長重複子字串」也是類似的。

Unique是出現一次，Repeat是出現兩次以上，兩者之間有著強烈的互補關係。

Minimal Unique Substring是只有出現一次、盡量縮短的子字串。它包含的子字串（自身除外），全部都是重複子字串；包含它的子字串，全部都是唯一子字串。

Maximal Repeated Substring是出現兩次以上、盡量延長的子字串。它包含的子字串，全部都是重複子字串；包含它的子字串（自身除外），全部都是唯一子字串。

按照定義，任取兩個Minimal Unique Substring，絕不會互相包含。Maximal Repeated Substring也一樣。

每當出現一個Minimal Unique Substring，位置是[i, j]，便存在兩個Maximal Repeated Substring：一個結尾是j-1、開頭小於i；另一個開頭是i+1、結尾大於j。

每當出現一個Maximal Repeated Substring，位置是[i, j]，便存在兩個Minimal Unique Substring：一個開頭是i-1、結尾小於等於j；另一個結尾是j+1、開頭大於等於i。

由此可知，Minimal Unique Substring和Maximal Repeated Substring是交錯出現的，兩者數量頂多差一。當原字串是De Bruijn Sequence，兩者數量達到極限。

注意到，當原字串包含連續的Unique Character，那麼交錯出現、數量差一的結論就不成立了。此時刻意定義Maximal Repeated Substring可以是空字串，以迫使結論成立。

給定所有的已排序的Maximal Repeated Substring，
求出所有的Minimal Unique Substring。

必須預先排序好。時間複雜度O(N)，N是Maximal Repeated Substring暨Minimal Unique Substring的數量。

const int R = 10; struct Interval {int a, b;} repeat[R], unique[R+1]; void repeat2unique() { int U = 0; if (repeat[0].a > 0) // 小心原字串開頭連續的unique character unique[U++] = (Interval){ 0, repeat[0].b + 1 }; for (int i=0; i<R-1; i++) // 小心連續的unique character unique[U++] = (Interval){ repeat[i+1].a - 1, repeat[i].b + 1 }; if (repeat[R-1].B < T-1) // 小心原字串結尾連續的unique character unique[U++] = (Interval){ repeat[R-1].a - 1, T-1 }; }

給定所有的Minimal Unique Substring，
求出所有的Maximal Repeated Substring。

必須預先排序好。時間複雜度O(N)，N是Maximal Repeated Substring暨Minimal Unique Substring的數量。

const int U = 10; struct Interval {int a, b;} unique[U], repeat[U+1]; void unique2repeat() { int R = 0; if (unique[0].a > 0) repeat[R++] = (Interval){ 0, unique[i].b - 1 }; for (int i=0; i<U-1; i++) // 小心空字串 repeat[R++] = (Interval){ unique[i].a + 1, unique[i+1].b - 1 }; if (unique[U-1].b < T-1) repeat[R++] = (Interval){ unique[N-1].a + 1, T-1 }; }

求出所有的Maximal Repeated Substring

時間複雜度O(N)。

const int N = 10; int sa[N], lcpa[N]; struct Interval {int a, b;} repeat[N]; int left[N]; // 區間[a,b]記錄為left[b] = a; void maximal_repeated_substring() { for (int i=0; i<N; ++i) left[i] = 1e9; for (int i=0; i<N; ++i) { // 找上一個後綴、下一個後綴，取LCP比較長的。 int lcp = lcpa[i]; if (i+1 < N) lcp = max(lcpa[i], lcpa[i+1]); // 如果不允許空字串，就取消if的註解。 // if (lcp > 0) // { int b = sa[i] + lcp - 1; left[b] = min(left[b], sa[i]); // } } int n = 0; for (int b=0; b<N; ++b) if (left[b] != 1e9) repeat[n++] = (Interval){left[b], b}; }

求出所有的Minimal Unique Substring

時間複雜度O(N)。

const int N = 10; int sa[N], lcpa[N]; struct Interval {int a, b;} unique[N]; int left[N]; // 區間[a,b]記錄為left[b] = a; void minimal_unique_substring() { for (int i=0; i<N; ++i) left[i] = -1e9; for (int i=0; i<N; ++i) { // 找上一個後綴、下一個後綴，取LCP比較長的。 int lcp = lcpa[i]; if (i+1 < N) lcp = max(lcpa[i], lcpa[i+1]); int b = sa[i] + lcp; if (b < N) left[b] = max(left[b], sa[i]); } int n = 0; for (int b=0; b<N; ++b) if (left[b] != -1e9) unique[n++] = (Interval){left[b], b}; }

Longest Common Extension

兩個字串，第一個字串從第i個字元開始，第二個字串從第j個字元開始，最長的相符字串，就是Longest Common Extension。

    01234567
s1: aabbccc
s2: aabbbccc

LCE(0, 0) = aabb
LCE(2, 2) = bb
LCE(3, 4) = bccc

Longest Common Extension其實就是第一個字串的第i個後綴、第二個字串的第j個後綴，它們的Longest Common Prefix。

演算法（Suffix Array）

把兩個字串的全部後綴，一起排序。如果有大量的i與j需要計算，可以使用Range Minimum Query來查詢LCP Array的區間最小值。

時間複雜度O(S+T)，S與T分別是兩個字串的長度。

演算法（Suffix Trie、Suffix Tree）

把兩個字串的全部後綴統統丟入Suffix Trie或Suffix Tree當中，從樹根往下逐字比對即可。如果有大量的i與j需要計算，可以改為求兩個後綴結尾節點的Lowest Common Ancestor。

時間複雜度O(S+T)，S與T分別是兩個字串的長度。

Longest Common Substring

「最長共同子字串」。出現於每一個字串的子字串，長度最長者。可能有許多個。

s1: aabbccc
s2: aabbbccc
s3: baabaccc

s1 s2 s3 的 Longest Common Substring 就是 aab 與 ccc。

演算法（Suffix Array）

把全部字串的全部後綴，標記好是屬於哪一個字串，然後統統排序。排在一起的後綴們，如果涵蓋了每一個字串的後綴，那麼這些後綴的共同前綴，就是一個共同子字串。所有的共同子字串當中，找出最長者，即為最長共同子字串。

實作時可以用兩個指標，一前一後輪流移動，讓兩個指標所夾住之區間，持有每一個字串的後綴，以找出共同子字串。

實作時可以把字串銜接成一整串，並在字串之間插入從未出現過的字元，就能直接套用後綴陣列的演算法。然而重新銜接字串會花費不少時間和空間，因此也可以嘗試修改後綴陣列的演算法，避免重新銜接字串。

時間複雜度O(N)，N是所有字串長度的總和。

【待補程式碼】

以下暫且提供未使用LCP Array的程式碼。

char s[10][1024]; // 10個字串，長度皆可達到1024-1。 char* sa[10 * 1024]; // suffix array int c[10]; // 記錄目前出現的後綴是位於哪幾個字串。 bool cmp(char* i, char* j) { return strcmp(i, j) < 0; } // 找出一個後綴所附屬的字串 inline int pos(int n) { // return (sa[n] - s[0]) / 1024; return (sa[n] - s[0]) >> 10; } // 求出兩個字串的Longest Common Prefix長度 int lcp(char* s, char* t) { int n = 0; while (s[n] && t[n] && s[n] == t[n]) n++; return n; } void longest_common_substring() { // 建立後綴陣列 int N = 0; for (int i=0; i<10; ++i) for (int j=0; s[i][j]; ++j) sa[N++] = s[i] + j; sort(sa, sa+N, cmp); // 尋找連續後綴 int ans = 0; memset(c, 0, sizeof(c)); for (int i=0, j=0, n=0; j<N; ) { // 往右移動j，直到涵蓋每一個字串的後綴。 // 並且隨時記錄每一個字串的後綴的出現次數。 while (n < 10 && j < N) if (!c[pos(j++)]++) n++; // 往右移動i，直到無法涵蓋每一個字串的後綴。 while (n == 10) if (!--c[pos(i++)]) n--; // 計算共同子字串，並且記錄最長者。 if (n == 10-1) ans = max(ans, lcp(sa[i-1], sa[j-1])); } cout << "最長共同子字串的長度是" << ans; }

UVa 11107 11512 11855 ICPC 3999

找到一個最短的字串，其子字串包含了所有給定字串。

NP-hard。

一個字串集合，從中挑選一些子字串，作為基礎，能夠拼出原本字串集合的每一個字串；子字串只能前後銜接、不能交疊。

比喻來說就是：給定一堆圖樣，請設計出一套七巧板的形狀，讓這套七巧板可以拼出所有給定的圖樣。某種程度上也近似Basis的概念。

NP-hard。