原理&实现

模板

inline void Extend(int id){
    int cur=++size,p=0,q=0,clone=0;
    maxlen[cur]=maxlen[last]+1;
    for (p=last;p&&!trans[p][id];p=Link[p]) trans[p][id]=cur;
    if (!p) Link[cur]=1;    else {
        q=trans[p][id];
        if (maxlen[q]==maxlen[p]+1) Link[cur]=q;
            else {
                clone=++size;   maxlen[clone]=maxlen[p]+1;
                memcpy(trans[clone],trans[q],sizeof(trans[q]));
                Link[clone]=Link[q];    Link[cur]=Link[q]=clone;
                for (;p&&trans[p][id]==q;p=Link[p]) trans[p][id]=clone;
            }
    }
    last=cur;
}

重要性质

1. 状态个数不超过2*n-1
2. 转移个数不超过3*n-4

应用

不同子串个数

考虑SAM每个节点的性质，每个节点包含了一系列连续长度的字符串，任意两个节点交集为空，所有节点的字符串的并集就是所有子串。那么

Ans=\sum_{i=1}^{size}maxlen[i]-minlen[i]+1

其中，

minlen[i]=maxlen[link[i]]+1

代码实现：

    for (i=2;i<=size;i++)   minlen[i]=maxlen[Link[i]]+1;
    for (i=2;i<=size;i++)   Ans+=(maxlen[i]-minlen[i]+1);

子串出现次数

每个子串必然属于一个状态，每个状态的endpos值就是该状态到结束状态的方案数。

可以先求一边拓扑序，然后倒叙求和即可。

[HAOI2016]找相同子串

题目大意

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

解法:

首先对第一个字符串建立SAM,然后让另一个字符串在上面跑。类似于KMP和AC自动机，可以利用link数组实现跳跃。然后考虑每一个子串，其可以视为从其末尾字符开始的一个后缀。如果得到了c[x-1]的匹配信息，那么利用上面的匹配方式，得到c[x]的匹配信息，然后

Ans=endpos[x]*(L-minlen[x]+1)

x为当前匹配到的状态。

上面的计算式子首先需要知道endpos的大小。可以通过在SAM上跑一遍原串，经过的位置的endpos值先记为1，然后求出SAM的拓扑序，逆序根据link数组累加计算。

同时上面的式子只考虑了x状态对答案的贡献，但是link[x],link[link[x]]均有贡献。这时需要在匹配完成的节点打上tag，在跑完字符串后，计算每一个状态对答案的额外贡献值。即可得到最后的答案。

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#define N 400010
#define LL long long
using namespace std;

int i,len,last=1,size=1,len2;
int minlen[N],maxlen[N],trans[N][26],l[N],v[N],z[N],in[N];
char c[N];
LL Ans;
LL r[N],f[N],cnt[N];

queue <int> Q;

inline void Extend(int x){
    int p=0,q=0,clone=0,cur=++size;
    maxlen[cur]=maxlen[last]+1;
    for (p=last;p&&!trans[p][x];p=l[p]) trans[p][x]=cur;
    if (!p) l[cur]=1;   else {
        q=trans[p][x];
        if (maxlen[p]+1==maxlen[q]) l[cur]=q;
        else {
            clone=++size;   maxlen[clone]=maxlen[p]+1;
            memcpy(trans[clone],trans[q],sizeof(trans[q]));
            for (;p&&trans[p][x]==q;p=l[p]) trans[p][x]=clone;
            l[clone]=l[q];  l[q]=l[cur]=clone;
        }
    }
    last=cur;
}

inline void Ready(){
    int i=0,x=1,j=0;
    for (i=2;i<=size;i++)   minlen[i]=maxlen[l[i]]+1;
    for (i=0;i<len;i++){
        x=trans[x][c[i]-'a'];   r[x]=1;
    }   r[x]=1;
    for (i=1;i<=size;i++)
        for (j=0;j<26;j++)
            (trans[i][j])?in[trans[i][j]]++:0;
    Q.push(1);  v[1]=1; z[++z[0]]=1;
    while (!Q.empty()){
        x=Q.front();    Q.pop();    v[x]=0;
        for (i=0;i<26;i++){
            if (!trans[x][i])   continue;
            in[trans[x][i]]--;
            if (!in[trans[x][i]]&&!v[trans[x][i]]){
                v[trans[x][i]]=1;   Q.push(trans[x][i]);
                z[++z[0]]=trans[x][i];
            }
        }
    }
    for (i=z[0];i;i--)  r[l[z[i]]]+=r[z[i]];
}

inline void Work(){
    int i=0,x=1,L=0,ch=0;
    for (i=0;i<len2;i++){
        ch=c[i]-'a';
        if (trans[x][ch]){
            L++;    x=trans[x][ch];
        }   else {
            while (!trans[x][ch]&&x)    x=l[x];
            if (!trans[x][ch])  {x=1;   L=0;    continue;}
                else L=maxlen[x]+1,x=trans[x][ch];
        }
        cnt[x]++;   Ans+=(LL)r[x]*(L-minlen[x]+1);
    }
    for (i=z[0];i;i--)  f[l[z[i]]]+=f[z[i]]+cnt[z[i]];
    for (i=2;i<=size;i++)   Ans+=(LL)r[i]*f[i]*(maxlen[i]-minlen[i]+1);
    printf("%lld\n",Ans);
}

int main(){
    freopen("find_2016.in","r",stdin);
    freopen("find_2016.out","w",stdout);
    scanf("%s",&c); len=strlen(c);
    for (i=0;i<len;i++) Extend(c[i]-'a');
    Ready();
    scanf("%s",&c); len2=strlen(c);
    Work();
    return 0;
}