后缀自动机学习.pdf

后缀自动机实质上是字母树,记录的字符串是某个字符串s的所有后缀.这里以字符串ACADD

为例:

这样很浪费空间和时间(实际上都是O(n^2)).但是,注意:这棵字母树的结点虽然多,但大部分结

点都只有一个儿子,而且有很多段是一样的.那么,利用公共部分,就可以对空间进行压缩,具体

地说,就是把自己连到儿子的边删掉(并把该儿子及其后代删掉),再把这条边连到别的子树,这

样就能充分利用公共部分,节省空间.但是,如何保证这样做和原来的笨做法是等价的,又如何

把时间复杂度和空间复杂度降到O(n)?这是个问题.幸运的是,后缀自动机出现了.

后缀自动机是这样的:在后缀自动机中,为了节省空间