[codevs3160]最长公共子串解题报告|后缀自动机

 给出两个由小写字母组成的字符串,求它们的最长公共子串的长度。

  样例就觉得不能更眼熟啊...好像之前用后缀数组做过一次

  然后发现后缀自动机真的好好写啊...(当然当时学后缀数组的时候也这么认为...

  

  这道题直接把第一个串放到后缀自动机里

  第二个串在上面做匹配,但是要注意匹配的时候不能乱搞...

  

  刚开始写了一个类似KMP的东西...想想不对啊

  毕竟有些节点的深度是不对的

  然而后来发现,我们可以用一个变量tem来保存当前的长度值

  如果可以继续匹配,这个值就+1

  否则就开始用fail指针不停地退,直到退到某个位置它的子节点中有当前字符了

  然后tem = 这个节点的深度+1

  我是这么理解的...通过观察后缀自动机的过程可以发现

  fail指针指向的节点都是深度确定的节点,如果深度不确定,会新建一个深度确定的点再指向它

  所以通过退fail指针得到的,这个节点的深度一定是对的

  然而它的子节点就不一定了...

  这也是为什么前面能够匹配的时候不能直接用长度...

原文地址:https://www.cnblogs.com/mjy0724/p/4478151.html