poj 3415 SAM後綴自動機
題意：
給出兩個串，問這兩個串的所有的子串中（重復出現的，只要是位置不同就算兩個子串），長度大於等於k的公共子串有多少個。
設A串構造SAM,B串去匹配A串
狀態再添加一個值：sum,指這個狀態出現多少次了。也就是說B串裡面有多少個子串可以進入這個狀態。
逆拓撲排序更新父親結點。
匹配過程中：
注意一點，匹配過程中進入某個狀態的串的長度是不固定的。
每次匹配長度lcs>=n時，當前狀態符合條件的子串的數量為：(lcs-max(n,p->f->len+1)+1)，這個數量是不固定的。這個狀態出現的次數為 p->right 。
如果p->f->len>=n，父親狀態是有符合狀態的子串，而且符合狀態的子串的數量是固定的。
先把這部分不固定的子串數量在匹配的過程中直接處理了。ans+=(lcs-max(n,p->f->len+1)+1)*p->right; 此時父親狀態出現的次數加一，p->f->sum++;
對於父親狀態，由於符合狀態的子串的數量是固定的，所以可以先把這個狀態出現的次數先求出來，等待匹配結束後再處理。
逆拓撲排序更新父親結點的出現次數
對於每個結點>=n的狀態
ans+=sam.pool[i].sum*sam.pool[i].right*(sam.pool[i].len-max(n,sam.pool[i].f->len+1)+1);
//出現次數*right集合大小*符合條件的子串數量
//len表示該狀態可以接受的最長的字符串長度，即max,
//那麼該狀態可以接受的最短的字符串長度為p->f->len+1
//子串儲存在狀態裡當且僅當字符串S,ST(S)！=NULL,S才為子串
//SAM 中的每個狀態能夠表示的不同子串的個數為 val - 父結點的 val
//所以在每增加一個點，或者說每次新建一個子父關系的時候，累加該狀態所產生的子串數量
//求子串出現的數量等於求所在狀態的right的集合大小，暫時還不會
#include
#include
#include
#include
#include
using namespace std;
const int maxn=100100;
struct suffixautomaton
{
struct node
{
long long len;//到這個狀態允許的最大長長度，即max(s)
long long right;//這個狀態在這個串裡有幾個位置，即right集合的大小
long long sum;
node *f,*ch[60]; //
node(){}
node(int l)
{
len=l;
f=NULL;
right=0;
sum=0;
memset(ch,0,sizeof(ch));
}
int calc() //返回該狀態包含的子串數量
{
if(f==NULL)return 0;//
return len-(f->len);
}
};
node *root,*last;
node pool[maxn*2]; //儲蓄結點用的
int cnt; //結點的數量
int tot; //當前sam可以表示的不同子串的數量，當建立子-父結點是，計算一次可以表示多少個子串
//當更改子-父關系時，必須先減去之前的狀態所表示子串數量
void init()
{
root=last=pool;
memset(root,0,sizeof(node));
cnt=1;
tot=0;
}
node * new_node(int l=0)
{
node *x=pool+cnt++;
memset(x,0,sizeof(node));
if(l!=0) x->len=l;
return x;
}
void add(char ch)
{
int c=ch-'A';
node *p=last,*np=new_node(last->len+1);
while(p&&!p->ch[c])
p->ch[c]=np,p=p->f;
if(NULL==p)
{
np->f=root; //建立子父關系
tot+=np->calc(); //計算增加的子串。下同
}
else
{
if(p->ch[c]->len==p->len+1)
{
np->f=p->ch[c];
tot+=np->calc();
}
else
{
node *q=p->ch[c],*nq=new_node();
*nq=*q; //nq也建立了子父關系，nq->f=q->f;
nq->len=p->len+1; //新建立nq
tot-=q->calc(); //q點要更換子父關系，先減去
q->f=np->f=nq;
tot+=q->calc()+nq->calc()+np->calc(); //此處新建三個子父關系
while(p&&p->ch[c]==q)
p->ch[c]=nq,p=p->f;
}
}
last=np;
}
int bus[maxn*2]; //處理
int sorted[maxn*2]; //0--（cnt-1）為拓撲排序的出序順序
void findr(char str[]) //處理某狀態的right集合的大小，如果想要找到位置，node必須有東西標志位置
{
int l=strlen(str);
memset(bus,0,sizeof(bus));
for(int i=0;ich[str[i]-'A'])->right++;
for(int i=cnt-1;i>0;i--)
if(pool[sorted[i]].f)
pool[sorted[i]].f->right+=pool[sorted[i]].right;
root->right=0; //還原
}
void solve() //求sum
{
node *p=root;
for(int i=cnt-1;i>0;i--)
if(pool[sorted[i]].f)
pool[sorted[i]].f->sum+=pool[sorted[i]].sum;
root->sum=0;
}
};
suffixautomaton sam;
char str[maxn];
char str2[maxn];
int main()
{
long long n;
while(scanf("%lld",&n),n)
{
scanf("%s",str);
sam.init();
int len=strlen(str);
for(int i=0;ich[c])
p=p->ch[c],lcs++;
else
{
while(p&&!p->ch[c]) p=p->f;
if(p==NULL) p=sam.root,lcs=0;
else lcs=p->len+1,p=p->ch[c];
}
if(lcs>=n)
{
ans+=(lcs-max(n,p->f->len+1)+1)*p->right; //由於其的不固定性。直接處理了
p->f->sum++;//父親出現次數加一
}
}
sam.solve();
for(int i=0;i=n) //對於符合的點，
ans+=sam.pool[i].sum*sam.pool[i].right*(sam.pool[i].len-max(n,sam.pool[i].f->len+1)+1);
}
printf("%lld\n",ans);
}
return 0;
}
