學習后綴自動機想法

小序：學習后綴自動機是要有耐心的，clj的論文自己看真心酸爽！（還是自己太弱，ls，oyzx好勁啊，狂膜不止）

　　　剛剛在寫博客之前又看了篇論文，終于看懂了，好開心

正文：

　　一.后綴自動機是什么？

　　　答：后綴樹+自動機

　　二.能處理什么問題？

　　　答：字符串之類的啊，還要問

　　三.有什么優點？

　　　答：代碼短，時間復雜度低

　　四.怎么寫？

　　　1.首先你得知道什么是自動機和什么是后綴樹？

　　　　這個是基礎問題，你可以去查查資料，本文不再闡述。

　　　2.后綴樹建樹點是N²的，怎么破？

　　　　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]+1=val[son[p][x]]則向np連一條為x的邊。否則執行步驟2.

　　　　　　　2.

　　　　　　　　

　　　　　　3.到這里你可能就要大喊一句為什么？為什么要新建節點？

　　　　　　　

　　　　 ? ? ?　　

　　　　　　論文上寫很好，你們如果不理解可以留言問我咯【本蒟蒻QQ：1481632287】

　　　五.總結：這個東西學起來有點難懂，但是學完了會發現還是很簡單的，雖說可能它的用處比后綴數組要小但是它的代碼短，又高效這才是更適合oi比賽的東東。

　　　　剛剛發現一個好強的博客：http://blog.csdn.net/wangzhen_yu/article/details/45481269；

　　　　

　　　　　　　

　　　　

　　　

　　　

?