整理下字符串的一些数据结构和算法

十二月 6th, 2012 1,456 留下评论 阅读评论

别看字符串挺简单,还真牵扯到好多数据结构和算法啊,给跪了,要将所有的都好好掌握真心是一项艰难的任务。这里就列举下自己做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——————————

 

Categories: ACM, 数据结构和算法 标签:,
  1. edward_mj | #沙发
    一月 6th, 2013 01:57

    学长写得好仔细……这种耐心真是自愧不如。 :twisted:

    • 求别黑……弱爆了……

icon_wink.gif icon_neutral.gif icon_mad.gif icon_twisted.gif icon_smile.gif icon_eek.gif icon_sad.gif icon_rolleyes.gif icon_razz.gif icon_redface.gif icon_surprised.gif icon_mrgreen.gif icon_lol.gif icon_idea.gif icon_biggrin.gif icon_evil.gif icon_cry.gif icon_cool.gif icon_arrow.gif icon_confused.gif icon_question.gif icon_exclaim.gif