CodeDevil

后缀自动机（SAM）是一个神奇的算法，它可以在O(n)的时间内搞出长度为n的字符串的所有子串。

花了一个晚上时间和杨主力一起讨论出来了。。。

窝们先看了CLJ的讲稿，然后发现完全搞不懂QAQ（一定是窝们的理解能力太差）

然后翻了下百度文库，发现《后缀自动机学习》写的很好，窝很能理解

于是就愉快地看懂啦！

然后再回头看CLJ的讲稿发现恍然大悟Orrrrrz

但是目前本蒟蒻只会SAM的板子。。。只能拿O(n)求子串来搞暴力

最后贴个板子上来吧。。。具体步骤看百度文库里的《后缀自动机学习》。

下一篇是SAM的应用0.0

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

using namespace std;

string s;

int p,q,np,nq,son[100010][26],fa[100010],len[100010],last=0,tot=0;

void Extend(char c)

{

len[++tot]=len[last]+1;

p=last;np=tot;

while (!son[p][c])

{

son[p][c]=np;

p=fa[p];

}

if (!p)

fa[np]=0;

else

{

q=son[p][c];

if (len[q]==len[p]+1)

fa[np]=q;

else if (len[q]>len[p]+1)

{

len[++tot]=len[p]+1;

nq=tot;

for (int k=0;k<26;k++)

son[nq][k]=son[q][k];

fa[nq]=fa[q];fa[q]=fa[np]=nq;

while (son[p][c]==q)

{

son[p][c]=nq;

p=fa[p];

}

}

}

last=np;

}

void Build_SAM(string s)

{

int i;

for (i=0;i<s.length();i++)

Extend(s[i]-'A');

}

void DFS(int p,string substr)

{

int i;

for (i=0;i<26;i++)

if (son[p][i])

{

cout<<substr+char(i+'A')<<endl;

DFS(son[p][i],substr+char(i+'A'));

}

}

int main()

{

string s;

cin>>s;

Build_SAM(s);

DFS(0,"");

return 0;

}