毕业设计指导网站建设,工商注册地址有什么要求,文案策划网站,凡科企业网站如何建设小序#xff1a;学习后缀自动机是要有耐心的#xff0c;clj的论文自己看真心酸爽#xff01;#xff08;还是自己太弱#xff0c;ls#xff0c;oyzx好劲啊#xff0c;狂膜不止#xff09; 刚刚在写博客之前又看了篇论文#xff0c;终于看懂了#xff0c;好开心 正文学习后缀自动机是要有耐心的clj的论文自己看真心酸爽还是自己太弱lsoyzx好劲啊狂膜不止 刚刚在写博客之前又看了篇论文终于看懂了好开心 正文 一.后缀自动机是什么 答后缀树自动机 二.能处理什么问题 答字符串之类的啊还要问 三.有什么优点 答代码短时间复杂度低 四.怎么写 1.首先你得知道什么是自动机和什么是后缀树 这个是基础问题你可以去查查资料本文不再阐述。 2.后缀树建树点是N2的怎么破 clj的ppt写的很详细但是不是很容易懂于是我这个蒟蒻就讲讲吧。 1.我们要破点又要能表示所有的状态势必就要合并点。 可是什么样的点是可以合并? 这可谓是后缀自动机学习需要了解的关键之一下面我就讲一下我的想法 我们首先要定义一个right数组表示一个子串s在母串ss中的右端点位置集合例如aab在aabaabab中的right[s]{3,6}; 这个有什么用呢 我们来想一个这样的问题如果两个串s1,s2的right集合有交集那会是什么情况 先给出结论等下在证明设sum[right[s]]代表right[s]集合的元素个数如果两个串s1,s2的right集合有交集并且sum[s1]sum[s2]则s1是s2的子串 证明设right[s1]∩right[s2]{v1,v2,v3.....,vk},就那v1来看吧那么s1和s2势必是v1前面的某两个点到v1所形成的字符串那么为什么sum[s1]sum[s2]则是s1是s2的子串一个显然的结论如果一个子串的sum更大那么它的长度越短。 证明了这些东西那么right集合相等的就可以合并了啊是不是很神,然后我们就可以利用right集合建一颗树了(可以表示出一个串的从属情况 如下图 这样就可以了吗能表示所有的子串状态吗显然是不行的不然要自动机干嘛可以自己yy一下。 2.状态数的线性证明. clj的ppt非常详细自己看看吧我怕我自己的证明不严谨将读者带入歧路。 3.构造过程 设已匹配串s待匹配字符x已建节点p。 1.新建节点np然后从p开始向fa[p]跳如果有连出为x的边并且val[p]1val[son[p][x]]则向np连一条为x的边。否则执行步骤2. 2. 3.到这里你可能就要大喊一句为什么为什么要新建节点 论文上写很好你们如果不理解可以留言问我咯【本蒟蒻QQ1481632287】 五.总结这个东西学起来有点难懂但是学完了会发现还是很简单的虽说可能它的用处比后缀数组要小但是它的代码短又高效这才是更适合oi比赛的东东。 刚刚发现一个好强的博客http://blog.csdn.net/wangzhen_yu/article/details/45481269 转载于:https://www.cnblogs.com/HQHQ/p/5547694.html
