Question

Count Substrings

C(n,2) + n + 1，分别统计长度大于一、等于一、等于零的子字串。时间複杂度 O(1)。

Count Distinct Substrings

利用 LCP Array，时间複杂度 O(N)。

Enumerate Substrings

演算法（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

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。

PKU 3693 UVa 10829

Shortest Unique Substring

Shortest Unique Substring

“最短唯一子字串”是只有出现一次的子字串当中，其长度最短者。可能有许多个。

Minimal Unique Substring 与 Maximal Repeated Substring

http://www.cas.mcmaster.ca/~bill/best/algorithms/11MinUnique.pdf

“极小唯一子字串”是区域极值，“最短唯一子字串”是全域极值，最短的“极小唯一子字串”就是“最短唯一子字串”。“极大重複子字串”与“最长重複子字串”也是类似的。

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 的数量。

Longest Common Extension

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

Longest Common Substring

“最长共同子字串”。出现于每一个字串的子字串，长度最长者。可能有许多个。

s1: aabbccc
s2: aabbbccc
s3: baabaccc

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

演算法（Suffix Array）

把全部字串的全部后缀，标记好是属于哪一个字串，然后统统排序。排在一起的后缀们，如果涵盖了每一个字串的后缀，那麽这些后缀的共同前缀，就是一个共同子字串。所有的共同子字串当中，找出最长者，即为最长共同子字串。

实作时可以用两个指标，一前一后轮流移动，让两个指标所夹住之区间，持有每一个字串的后缀，以找出共同子字串。

实作时可以把字串衔接成一整串，并在字串之间插入从未出现过的字元，就能直接套用后缀阵列的演算法。然而重新衔接字串会花费不少时间和空间，因此也可以尝试修改后缀阵列的演算法，避免重新衔接字串。

时间複杂度是 O(N)，N 是所有字串长度的总和。

【待补程式码】

以下暂且提供未使用 LCP Array 的程式码。

Shortest Common Superstring

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

http://www.cs.sunysb.edu/~algorith/files/shortest-common-superstring.shtml

NP-hard。

Minimum Substring Cover

一个字串集合，从中挑选一些子字串，作为基础，能够拼出原本字串集合的每一个字串；子字串只能前后衔接、不能交叠。

比喻来说就是：给定一堆图样，请设计出一套七巧板的形状，让这套七巧板可以拼出所有给定的图样。某种程度上也近似 Basis 的概念。

NP-hard。