Question

String

“字串”。一连串字元。字串的长度就是字元数目。

例如 aaabbbccc、48Dfua@~!0H、m、How are you?。

有个特例是空字串：一个字元都没有的字串，长度为零的字串。通常标记成Ø。

Character

“字元”。字串的基本单元。

例如字串 How are you?的字元依序为：H、o、w、 、a、r、e、 、y、o、u、?。第一个字元是 H，第四个字元是空白符号 ，最后一个字元是问号?。

例如字串“你好吗？”的第二个字元是“好”，第四个字元是全形问号“？”。

ASCII Table 规定了电脑中基本的 128 种字元，包括大写小写英文字母、标点符号、阿拉伯数字、数学运算符号、杂七杂八的符号。

Substring

“子字串”。字串当中的一段字串。

例如 algo 的子字串一共是Ø, a, l, g, o, al, lg, go, alg, lgo, algo。

Prefix

“前缀”。字串开头的一段字串。

例如 algo 的前缀一共是Ø, a, al, alg, algo。

Suffix

“后缀”。字串尾端的一段字串。

例如 algo 的后缀一共是Ø, o, go, lgo, algo。

Sequence

“数列”。一连串数字。数列的长度可以达到无限长。

例如 1 2 3 4 5、1 1 2 3 5 8 ...。

字串学当中，习惯译作“序列”而不是“数列”，习惯讨论有限长度的数列，习惯把数列当作字串。

字串与数列唯一的差异在于：字串的字元是有限多种；数列的数字是无限多种。屏除这项差异之后，字串与数列完全相同，字串可以视作数列、数列可以视作字串。

Subsequence

“子序列”。字串当中由左到右挑取字元所构成的字串。

例如 algo 的子序列一共是Ø, a, l, g, o, al, ag, ao, lg, lo, go, alg, alo, ago, lgo, algo。

String 资料结构: Array

Array

字串的字元依序填入阵列，最后用一个特殊符号标记字串结尾。

要不然也可以记录最后一个字元的索引值、指标，这样就不用加特殊符号。要不然也可以记录字串长度，数值比前者多一。

缺点是插入字元、插入字串很慢，后方字元必须通通往后挪。

可以直接使用 STL 的 string。

UVa 10252

String 资料结构: Rope

Rope

https://en.wikipedia.org/wiki/Rope_(data_structure)

字串的子字串依序填入平衡二元树的树叶。树叶是阵列。

简述其中几个操作：

印出字串：DFS 遍历所有节点。令 N 是字串长度，树叶最多 N 个，节点最多 2N-1 个，时间複杂度 O(N)。

索引（取第 K 个字元）：令节点储存子字串长度。从根往叶走，找到第 K 个字元所在树叶，再从阵列取得第 K 个字元。时间複杂度 O(logN)。

衔接字串：两棵树，新增一个共同的树根。令节点储存子树高度，以平衡高度。时间複杂度 O(logN)。

插入字串：从第 K 个字元切开，分枝成两个新树叶。其中一个树叶再分支成原树叶、新树。时间複杂度 O(logN)。

熟悉二元树，就能轻鬆推理出来，不必记诵。

大量 String 资料结构: Array

Dictionary

储存大量字串的资料结构，大家通称为 Dictionary。就好比拥有即时排序功能的资料结构，大家通称为 Priority Queue。

这些泛称是用来凸显资料结构的功能。有了这样的泛称，当遇到的问题隐含著字典的概念，就能直觉联想到 Dictionary 资料结构，而不会被 Array、BST 这种不直觉的名称困住了思考。

Array

各种经典的资料结构，皆可储存大量字串，例如阵列。

Hash Table

使用字串杂凑函数，将字串化作索引值，存入 Hash Table。

经典的字串杂凑函数有 djb2、sdbm、murmur3。

可以直接使用 STL 的 hash，不清楚是 murmur 哪一版。

大量 String 资料结构: Binary Search Tree

Binary Search Tree

二元搜寻树，一个节点储存一个字串。

UVa 148 156 245 642 630 10295 10282 10686 10896 429 10150

Ternary Search Tree

三元搜寻树，一个节点储存一个字元。左小孩是更小与相同的字串，右小孩是更大的字串，中小孩是原字串的后续字元。三元搜寻树与二元搜寻树等价。

大量 String 资料结构: Trie

Trie【翻译成“橱”似乎不错】

Trie 是一棵特别的树，一条由根往叶的路径是一个字串。节点含有阵列，以阵列索引的方式进行纪录，每一层的节点分别对应字串的每一个字元。

举个简单的例子。假设字元只有 abcde 五种。

储存字串 abc：由树根往下走，每一层的节点依序对应字串的每一个字元。多出来的树叶，用来标记字串结尾，可以想成是'\0'。

再储存字串 aeb：开头相同的部分，归併在一起。

这种储存字串的方式，类似于编排字典的方式，减低了检索单字的困难度。Trie 可以想作是多层次的索引表。

相信各位对 Trie 的储存方式已经驾轻就熟了。优点是速度飞快，缺点是耗费记忆体。最后提供 Trie 的常见图示方式。

UVa 902 10226 10391 10745

设计 Trie 的节点

ASCII 一共有 128 种字元，一个节点只需要一条 128 格阵列。

如果遇到 abc 和 abcde 这种一个字串是另一个字串的前缀的例子，就无法判断字串结尾。此时必须用一个变数判断字串结尾。如此一来也可以储存空字串了。

如果字串可以重複出现，就用一个变数累计出现次数。

初始化。大功告成。

增加一个字串

时间複杂度是 O(S)，其中 S 是字串的长度。

寻找一个字串（判断字串存不存在）

时间複杂度是 O(S)，其中 S 是字串的长度。

依照顺序印出所有字串

DFS 走访每个节点。时间複杂度等同于 Trie 的节点数量。

释放记忆体空间

写了 new 而不写 delete 是大逆不道的事情！一定要记得写！

Double-Array Trie

所有节点合併成一条极长阵列，另外用一条阵列记录节点大小、节点位置。

优点是删除了 Trie 的阵列末端空格，缺点是必须动态配置节点大小、节点位置。省空间、费时间。

动态配置节点，大可不必自己实作，可以直接使用 malloc/free、new/delete。

Compressed Trie

去掉没有分岔、呈一直线的节点。

去掉节点之后，字串资讯不完整，必须做点处理：

一、每个节点增加一个数字，记录当前是第几个字元。也就是开始分岔的字元。

二、在树叶裡储存完整字串。每个节点增加一个指标，记录当前节点要参考哪一个树叶的字串。

三、或者，在节点裡储存片段字串，代价是必须动态配置字串空间大小。省空间、费时间。

大量 String 资料结构: Automaton

Automaton

自动机主要用于字串验证（string verification）。依序读取字串的各个字元，同时在自动机上移动；一旦字串读取完毕、正好抵达自动机终点，那麽字串验证成功。

自动机亦可用于字串匹配（string matching）。许多字串匹配演算法，都可以顺势建构自动机，请参考“ String Matching ”。

自动机的特色是：仰赖一个 lookup table，只需要反覆查表，就能完成字串验证、字串匹配，而不需要特别的演算法。

以图论的观点来看，先前章节都是用树来储存字串，此处则是用图来储存字串。然而图的结构太过複杂，导致自动机难以建构，也无法直接插入字串、删除字串、枚举字串，只能搜寻字串。

列出字串很慢，验证字串很快，自动机有著 NP-complete、one-way function 的味道。

UVa 251 738 804 ICPC 4358

DAWG

https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton

Online Compact DAWG

http://www.shino.ecei.tohoku.ac.jp/~ayumi/papers/DAM2004_cdawg.pdf

String Manipulation

String Manipulation

http://en.wikipedia.org/wiki/String_function

程式语言的内建函式库，已经囊括所有常见的字串操作函式，建议读者仔细研究。

UVa 483 492

以下额外整理了一些稀奇古怪的字串操作。通常只会出现在求职面试的益智测验，平常极少用到。

Rotate

循环位移 n 个元素，只使用 swap、不使用额外空间。时间複杂度 O(N)。

Lyndon Word 是指所有旋转结果当中，字典顺序最小者。时间複杂度 O(N)。

http://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation

UVa 719 ICPC 2755

要判断两个字串旋转后是否相等，时间複杂度 O(N)。

要判断两个字串旋转后是否相等，也可以运用字串比对：判断 aa 是否出现 b，时间複杂度 O(N)。

Interleave

字串 A 之中，由左到右参差穿插字串 B，判断是否可以形成字串 C。

A 和 B 的全部字元就是 C 的全部字元。A 和 B 都会是 C 的子序列。

A = abc
B = xyz
C = axbycz, xaybzc, abxycz, abcxyz, xyzabc, ......
C != cbaxyz, abyxcz, ......

当 A 和 B 没有共同的字元，得以採用 Greedy Method，时间複杂度 O(A+B)。

当 A 和 B 有共同的字元，只能採用 Dynamic Programming，分割问题的方式等同 Longest Common Subsequence，时间複杂度 O(A*B)。程式码就不提供了。

Cover

从字串 A 找出最短的子字串，包含字串 B 每一种字元。时间複杂度 O(N)。

http://www.cs.ucr.edu/~stelo/cpm/cpm10/23.pdf
http://www.cas.mcmaster.ca/~bill/best/algorithms/02AllCovers.pdf
http://stackoverflow.com/questions/2459653

Input string 1: "this is a test string"
Input string 2: "tist"
Output string: "t stri"

how can I approach towards finding smallest substring of string 1
that contains all the characters from string 2?
O(N) histogram

Concatenate

给定一个长字串与一堆短字串。现在要将短字串衔接成长字串，短字串得重複使用。判断是否只有唯一一种衔接方式。

Sardinas-Patterson Algorithm。