-Flyぁ梦-

别看字符串挺简单，还真牵扯到好多数据结构和算法啊，给跪了，要将所有的都好好掌握真心是一项艰难的任务。这里就列举下自己做zoj时候碰到过的一些，然后配合自己做过的例题讲一下。不过每种算法、数据结构具体的描述和代码，还请自己去搜索吧。

算法

KMP算法

字符串在普通项目中用得最多的必然是匹配和查询问题了，KMP算法通过O(M)的时间预处理短串，然后在O(N)的时间内搜索长串得到结果，算是最经典的字符串匹配算法了，其中预处理字符串next数组的方法非常具有扩展性。KMP并不太容易懂，推荐百度搜索“Matrix67 KMP”这篇文章，比较好懂。自己写一遍KMP再配合着OJ做一些题，就有感觉了。

zoj 2177 Period : 由重复子串不重叠构成的所有前缀。这里用到了next函数的思想。

zoj 2177 Crack : int值的KMP。搜索到串后，再分别往前往后继续匹配，比较最大值。

zoj 3587 Marlon’s String : 串A和串B，求出A[i1, j1] + A[i2, j2] = B有多少种。KMP中每一次i与j的匹配都意味着一个前缀的匹配，后缀通过字符串反序同理前缀处理。

zoj 3643 Keep Deleting : KMP和栈的结合。

最小表示法

一个字符串按照字典序的最小表示序列。可以用来判断某些字符串是否循环同构。

一开始看懂了，最近又忘了，不过知道有这个算法，应用起来套进去好像比较容易。

zoj 1729 Hidden Password : 求字符串的最小表示位于原字符串的位置。

Manacher算法

用来求一个字符串中最长回文子串的算法，比用后缀数组的方案既快又节约内存。没怎么看懂，好像也就这么个用途，勉强记得有这个算法吧 =.=。

poj 3974 Palindrome : 求最长回文子串的长度。

栈处理

主要是字符串里的括号匹配的问题，很容易想到用栈。

zoj 1423 (Your)((Term)((Project))) : 删除多余的括号。

zoj 2483 Boolean Expressions : 计算布尔表达式的值。

zoj 2704 Brackets : 判断带圆括号和方括号的表达式是否正确。

数据结构

Trie树

这算是最简单的了，很容易看懂和应用的数据结构。用来查找某些字符串是否存在于一个字符串集合当中，查找花费O(N)的时间（这里用Java的HashMap和String自带的hashCode方法，也比较不错）。Trie树适合被搜索对象是一个word，搜索其是否整体匹配单词源集合某一个。

zoj 1109 Language of FatMouse : Trie树最基础应用

zoj 1888 Zipf’s Law : 查找一段文章中出现次数为N的单词。也是Trie树普通运用，最后选择遍历Trie树也可以，当然也可以优化下。

zoj 2346 Shortest Prefixes : N个串，将每个串缩短至最短的前缀串来唯一表示这个串，但在N个串中不能有冲突。

AC自动机 – Trie树升级版

AC自动机，就是在Trie树的基础上给每个节点加一个fail指针，类似KMP的next数组的感觉，每次匹配失败后可以继续向前匹配。为什么叫自动机呢，学过计算理论应该还是比较好理解的。AC自动机的建立，在Trie树已经建立后，加一步建立fail指针的过程，需要通过bfs遍历一遍Trie树。然后搜索的时候没匹配一个节点，都要依次循着fail指针向上查询直到root节点查找是表示为串结尾的节点，这些都是符合的情况。

AC自动机适合处理那些一长段文字中去寻找某些个单词的情况，即适合被搜索对象是一个长串，搜索其部分匹配单词源集合。

附上一份自己写的AC自动机的代码，Click here。

zoj 3228 Searching the String : 可重叠和不可重叠地去查询某个串存在的次数。

zoj 3430 Detect the Virus : Base64解码后再匹配。题目比较恶心…然后这里字符集有256个，包括’\0’，所以用insert(char *s, int len)比较好，然后很恶心的一点习惯写Java后才发现C++的char默认是signed的…这里要转换成unsigned char，不然OJ上就不断地SF了。

后缀树和后缀自动机

将一个字符串的所有后缀作为不同的串，插入到Trie树形成的树，同理再加上fail指针就是后缀自动机。后缀树和后缀自动机都是对一个长串进行某些处理，比如寻找某些子串、寻找最长回文子串、寻找两个串的某些共同属性（比如最长公共部分等）。但是后缀树算法和程序比较复杂，做题的时候好像很少用到，而是用较为简易的后缀数组的来代替。

后缀数组

后缀树的简化版本，用几个数组来记录后缀串的不同属性。网上流行的模板代码里，sa数组按字典顺序记录后缀的序号（ra[rk] = index），rank数组与sa数组互逆，按照后缀序号记录后缀的字典序大小（rank[index] = rk）。然后为了模拟后缀树，还有height数组，记录height[i] = LCP(ra[i – 1], ra[i])，LCP为Longest Common Prefix（最长公共前缀），即有了后缀树里的Least Common Ancestors（最近公共祖先）的意思。后缀数组开了这么多数组比较耗费内存，所以不适合字符串长度很长（超过一百万）的题目。

建立后缀数组，有两种比较复杂难懂的算法，倍增算法和DC3算法，前者O(NlogN)后者O(N)的复杂度，反正LZ看不懂也不会写用的也是网上找的模板。计算height值是O(N)的算法，也不懂。任意两个后缀的LCP值是它们sa值之间的height值的最小值，这里包含了一个RMQ（Range Minimum Query）问题。

后缀数组的详细可以看一下《后缀数组—处理字符串的有力工具》这篇高中生写的论文，膜拜…虽然觉得里面某些代码和题解有点问题，不过算法描述很详细很值得去读而理解。

附上一份网上找的蛮好用的后缀数组代码，Click here。

ural 1297 Palindrome : 求最长回文子串。poj也有类似一题但是数据量太大，可以用前面提到的Manacher算法求解。

zoj 2737 Occurrence : 求串B所有的循环同构串在串A中出现的次数和。解决循环的办法就是设B’ = B + B，S = B’ + ‘$’ + A，然后对S进行后缀数组处理。

zoj 3199 Longest Repeated Substring : 含有不可重叠且连续子串的子串。

zoj 3296 Connecting the Segments : 这道题真是牛逼了，结合了后缀数组、RMQ、贪心之最小区间覆盖，很经典很值得一练的题。后缀数组的作用并不是求出所有的回文子串（无法求出被真包含的回文子串，比如aabaa，aabaa本身是回文子串，其中真包含的aba也是回文子串，aba就无法得到），但是不影响区间覆盖。

zoj 3395 Stammering Aliens : 可重叠子串多于k个。这里需要将height数组分组，很多后缀数组的题目都需要如此处理，原因就是上面提到的LCP取最小值。

学习后缀数组真心花了好多天，一开始只会按照套路和题解去套用后缀数组的方法解题，做了几个题目就慢慢理解后缀数组的意义所在，就能自己想办法去利用后缀数组了。不做题，不coding，理解不了，但是痛苦的是一段时间不做的话又会忘了，这个怎么破 T_T。

——————————-to be continued——————————