后缀树
后缀树(Suffix tree)是一种数据结构，能快速解决很多关于字符串的问题。后缀树提出的目的是用来支持有效的字符串匹配和查询。
学习后缀树之前，先了解一下Trie这个数据结构Trie是一种搜索树，可用于存储并查找字符串。Trie每一条边都对应一个字符。在Trie中查找字符串S时，只要按顺序枚举S的各个字符，从Trie的根节点开始选择相应的边走，如果枚举完的同时恰好走到Trie树的叶子节点，说明S存在于Trie中。如果未到达叶子节点，或者枚举中未发现相应的边，则S没有被包含在Trie中。
后缀树就是一种压缩后的Trie树。
比如 S：banana，对S建立后缀树。
首先给出S的后缀们
0：banana
1：anana
2：nana
3：ana
4：na
5：a
6：空
为了更清楚的表示后缀，我们在后缀的后面加上$
0：banana$
1：anana$
2：nana$
3：ana$
4：na$
5：a$
6：$
然后对其进行分类：
5:a$
3:ana$
1:anana$
0:banana$
4:na$
2:nana$
6: $
后缀树的应用：
example 1：在树中查找an(查找子字符串)
example 2：统计S中出现字符串T的个数
每出现一次T，都对应着一个不同的后缀，而这些后缀们又对应着同一个前缀T，因此这些后缀必定都属于同一棵子树，这棵子树的分支数就是T在S中出现的次数。
example 3：找出S中最长的重复子串，所谓重复子串，是指出现了两次以上。首先定义节点的“字符深度” = 从后缀树根节点到每个节点所经过的字符串总长。找出有最大字符深度的非叶节点。则从根节点到该非叶节点所经过的字符串即为所求。
后缀树的用途，总结起来大概有如下几种 :
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进行快速定位， 在合适的地方插入新的节点。
不断重复以上步骤，即可完成后缀树的构造。
后缀树代码如下：
//SuffixTree.h
typedef struct node //声明节点的结构
{
string strdata; //存储节点上的字符串
vector Child; //存储该节点的子节点的地址
int flag; //辅助标志位,用0和1表示该节点是否有子节点
int breakpoint; //辅助变量,当该节点需要分裂时,用于记录分裂点的位置
}*mynode;
classCSuffixTree
{
public:
mynode ST; //ST生成的后缀树的根节点
mynode point; //point节点指针，搜索时指向搜索节点的父节点，搜索结束时根据搜索
//结果指向要操作的节点
CSuffixTree(string str);
~CSuffixTree(void);
int Search(string str);
void CreatTree();
void Show(mynode ST);
void PrintNode(mynode p, int c, vector& isend);
private:
string data; //data源字符串变量，在构造函数中初始化
string left; //left用于记录每次搜索结束后，目标字符串中的剩余字符串
};
//SuffixTree.cpp
//构造函数，初始化data变量和ST,point指针并产个根节点的第一个子节点，ST的flag置1
CSuffixTree::CSuffixTree(stringstr)
{
data = str;
ST = (mynode) new node;
point = (mynode) new node;
point->strdata = data[0];
point->flag = 0;
ST->Child.push_back(point);
ST->flag = 1;
}
//析构函数
CSuffixTree::~CSuffixTree(void)
{
}
voidCSuffixTree::CreatTree()
{
int i, j, n, h, ic, jc;
string temp;
string tempuse;
mynode cnode;
for (i = 1; i <= (data.length()-1); i++)//调用两层循环，产生目标字符串每一个前缀的所 有后缀
{
for (j = 0; j <= i; j++)
{
temp.erase(temp.begin(),temp.end());
ic = i;
jc = j;
for (; jc <= ic; jc++)
{
temp.insert(temp.end(), data[jc]);
}
n = Search(temp); //调用Search函数搜索生成的字符串
switch (n)
{
case (-1)://分裂节点，父分裂点为point->breakpoint
tempuse =point->strdata;
cnode=(mynode) new node;
if (point->Child.size() !=0)
{
cnode->Child =point->Child;
}
cnode->flag =point->flag;
point->Child.erase(point->Child.begin(),point->Child.end());
point->strdata.erase(point->strdata.begin(),point->strdata.end());
for (h = 0; h<(point->breakpoint); h++)
{
point->strdata.insert(point->strdata.end(),tempuse[h]);
}
for (h =(point->breakpoint); h < p>
{
cnode->strdata.insert(cnode->strdata.end(), tempuse[h]);
}
point->Child.push_back(cnode);
cnode = (mynode) new node;
cnode->strdata = left;
cnode->flag = 0;
point->Child.push_back(cnode);
point->flag = 1;
break;
case (0)://do nothing
break;
case (1)://在叶节点point处追加left字符串
point->strdata =point->strdata+left;
break;
case (2)://在父节点point下添加子节点cnode
cnode = (mynode) new node;
cnode->strdata = left;
cnode->flag = 0;
point->Child.push_back(cnode);
point->flag = 1;
break;
}
}
}
}
//返回1: 则在指针point所指向的节点的strdata后追加 left字符串
//返回2: 则生成point所指向的节点的子节点，子节点的strdata值为left字符串
//返回0: 则donothing
//返回-1:则分裂节点将分裂点写入point指针所指向的 节点的breakpoint，并将目标字符串的剩余字符串写入left
intCSuffixTree::Search(string str)
{
stack s;
int i, n = 0;
mynode child;
char target;
point = ST; //初始搜索位置为根
child = NULL;
for (i = (str.length()-1); i >= 0; i--)//将目标字符串str压栈
{
s.push(str[i]);
}
while(!s.empty())//直到搜索完str串
{
//寻找point所指向的节点下与str首字母相同的子节点
for (i = 0; i <=(point->Child.size()-1); i++)
{
if(point->Child[i]->strdata[0] == s.top())
{
child =point->Child[i]; //child指针指向与str具有相同首字母的节点
break;
}
}
if (child == NULL)//父节点point下没有首字母相同的子节点
{ //将str中剩余的字符串保存在left中
left.erase(left.begin(),left.end());
while(!s.empty())
{
left.insert(left.end(),s.top());
s.pop();
}
return (2);
}
target = s.top(); //
s.pop();
if (1)
{
//child节点下的每个字符与str中的字符顺序比较
for (i = 0; i <=(child->strdata.length()-1); i++)
{
if (child->strdata[i] ==target)
{
if (!s.empty())
{
target = s.top();
s.pop();
continue;
}
else return(0); //若str中的字符串先于strdata中的字符串完成比较，则说明该字符 //串已经包含在树中
}
else //比较中出现不同，需要分裂节点
{
point = child; //point指向要分裂的节点
left.erase(left.begin(),left.end()); //将str中剩余的字符串写入left
s.push(target);
while(!s.empty())
{
left.insert(left.end(),s.top());
s.pop();
}
point->breakpoint =i; //写入父节点point的分裂点
return (-1); //分裂节点
}
}
point = child; //走出循环则进行下一个节点的搜索
if (!point->flag)//判断刚刚搜索的是否为叶节点，若是则停止搜索
{
left.erase(left.begin(),left.end());
s.push(target);
while(!s.empty())
{
left.insert(left.end(),s.top());
s.pop();
}
return (1);
}
s.push(target);
child = NULL;
}
}
//字符串str搜索完成，仍没有到达叶节点，返回0
return(0);
}
voidCSuffixTree::Show(mynode m_pSTreeRoot)
{
vector bIsEnd;
bIsEnd.push_back(0);
cout << "Root" << endl;
for(int i = 0; i <(int)m_pSTreeRoot->Child.size(); i++)
{
if(i ==(int)m_pSTreeRoot->Child.size() - 1)
{
bIsEnd[0] = 1;
}
PrintNode(m_pSTreeRoot->Child[i], 1,bIsEnd);
}
cout << endl;
}
voidCSuffixTree::PrintNode(mynode p, int c, vector& isend)
{
for(int j=0; j<>
{
if(isend[j] == 0)
{
if(j != c-1)
cout << "│";
else
cout << "├";
}
else
{
if(j != c-1)
cout << " ";
else
cout << "└";
if(j != c-1)
cout << " ";
else
cout <<""; //最后一个
}
}
cout << " " //if(p->Child.size() == 0)cout <<" (" << p->nIndex << ")"; cout << endl; for(int i=0; i<(int)p->Child.size();i++) { if(isend.size() == c) { isend.push_back(0); } else { isend[c]=0; } if(i == (int)p->Child.size() - 1) { if(isend.size() == c) isend.push_back(1); else isend[c]=1; } PrintNode(p->Child[i], c + 1,isend); } } //mian.cpp intmain(int argc, char* argv[]) { string a; cout << "Please input astring:"; cin >> a; //通过输入获得目标字符串a CSuffixTree mytree(a); //产生CsuffixTree类的实例mytree mytree.CreatTree(); //调用CreatTree方法创建一棵后缀树 mytree.Show(mytree.ST); //调用Show方法输出生成的后缀树 }
济宁人力资源和社会保障局济宁2015年下半年软考证书领取联系电话
[考试动态]2016年4月26日邹城人力资源和社会保障局邹城2015年下半年软考补办证书合格人员名单
[考试动态]2016年4月26日邹城人力资源和社会保障局邹城2015年下半年软考证书领取联系电话
[考试动态]2016年4月26日邹城人力资源和社会保障局邹城2015年下半年软考证书领取办理方式
[考试动态]2016年4月26日邹城人力资源和社会保障局邹城2015年下半年软考合格人员名单
[考试动态]2016年4月26日