【后缀自动机】【SAM】【自动机】【数据结构】后缀自动机理解(
引入
样例我们同样以下面的例子来介绍后缀自动机我们看一看下面使用abc串构建的简单的后缀自动机 这里我们讲一下这样的定义我们令 概念这里我们再讲一个概念:我们可以发现任意一个节点可以构成许多个子串比如:上面的图中b节点就同时代表了a和ab两个子串,同时我们可以发现在字符串中a和ab的结尾位置是相同的,所以我们认为每个节点也表示了一个终点位置的集合 重点:且这些同一个节点的字符串的结束位置全部相同,如果这个时候a在字符串的另一个位置也出现的话,那么我们就不能这样表示了。 结论一我们可以假设当前节点表示的字符串最长为R,最短为L那么我们可以发现因为L必定为R的后缀那么同时又有L最短,那么如果有mid处于L和R的长度之间,那么我们一定有mid的出现次数相同且L为mid的后缀那么mid必定在当前节点表示的子串中,那么我们可以发现任意一个节点表示的字符串长度是有一个范围的连续区间组成的 结论二我们来观察一下上面的图片发现一下虚线到底维护了一个怎样的性质? 结论三只有最后的c节点(last)节点和他的虚线连接的边可以作为当前整个已经添加节点的字符串的后缀(根据上面的两个结论可以很容易得到当前的结论) 实际操作其实知道了这几个结论我们就可以开始做题了,我们先举一个例子看看如果构建自动机:abaa首先第一步是一个空串root 冲突与完善就继续使用上面的例子我们现在匹配abaaa那么此时我们还需要添加一个a到上图中去,显然第一步:将
代码void Insert(int c){
node *np = ++ecnt,*p = last;
np->len = last->len+1;
last = np;
while(p&&!p->ch[c])
p->ch[c]=np,p=p->fail;
if(!p)
np->fail = root;
else{
node *q = p->ch[c];
if(p->len+1 == q->len){
np->fail = q;
}else{
node *nq = ++ecnt;
*nq = *q;
nq->len = p->len+1;
np->fail = nq;
q->fail = nq;
while(p&&p->ch[c]==q)
p->ch[c]=nq,p=p->fail;
}
}
}
相关习题[SPOJ LCS]Longest Common Substring: 题解 感谢感谢您阅读本篇博客,如果有什么写的不好的地方求留下评论(谢谢) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |