2011年软考程序员考试复习笔试知识点整理(17)

　　后缀树的用途，总结起来大概有如下几种 :

　　1. 查找字符串o是否在字符串S中

　　方案：用S构造后缀树，按在trie中搜索字串的方法搜索o即可。

　　原理：若o在S中，则o必然是S的某个后缀的前缀。

　　听起来有点拗口，举个例子。例如S: leconte，查找o: con是否在S中,则o(con)必然是S(leconte)的后缀之一conte的前缀。有了这个前提，采用trie搜索的方法就不难理解了。

　　2. 指定字符串T在字符串S中的重复次数

　　方案：用S+'$'构造后缀树，搜索T节点下的叶节点数目即为重复次数 。

　　原理：如果T在S中重复了两次，则S应有两个后缀以T为前缀，重复次数就自然统计出来了。

　　3. 字符串S中的最长重复子串

　　方案：原理同2，具体做法就是找到最深的非叶节点。

　　这个深是指从root所经历过的字符个数，最深非叶节点所经历的字符串起来就是最长重复子串。为什么要非叶节点呢?因为既然是要重复，当然叶节点个数要>=2。

　　4. 两个字符串S1，S2的最长公共部分

　　方案：将S1#S2$作为字符串压入后缀树，找到最深的非叶节点，且该节点的叶节点既有#也有$(无#)。大体原理同3。

　　//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

　　后缀树的存储：为了节省空间，我们不在边上存储字符串，而是存储该字符串在原串中的起止位置，空间复杂度O(n)。

　　后缀树的构造：最简单的方法，使用Trie的构造方法，时间复杂度为O(n^2);

　　后缀树也可以在O(n)的时间复杂度内构造，但比较复杂。

　　如，基本思路：先向后缀树中插入最长的后缀串(S本身)，其次插入次长的后缀串，以此类推，最后插入空串。定义后缀链接(Suffix Link)=从节点A指向节点B的指针，B所表示的子串是A所表示的子串的最长后缀。既，根节点到A所经过的字符串s=aw，则从根节点到B所经过的字符串为w。

　　算法所用符号描述：

　　后缀树的构造，算法流程：

　　1)定义SL(root)=root，首先插入S，此时后缀树仅有两个节点。

　　2)设已经插入了S(i),现在要插入S(i+1)，分两种情况讨论：

　　1：P(S(i))在插入之前已经存在，(如，na，ana，a是na的parent)，则P(S(i))有后缀链接，令u=SL(P(S(i)))，从u开始沿着树往下查找，在合适的地方插入。

　　2：P(S(i))是插入S(i)过程中产生的，此时G(S(i))必定存在并有后缀链接，比如(na，ana，bana)，令u=SL(G(S(i)))，w=W(G(S(i)),P(S(i))).从u开始，对w进行快速定位， 在合适的地方插入新的节点。

　　不断重复以上步骤，即可完成后缀树的构造。

　　软考程序员考试历年真题重点题总结及答案

　　2011年上半年软考报名时间及方式汇总

　　软考程序员考试历年真题汇总(2007年-2010年)