[NOI Online 2021 提高组] 积木小赛

观察到我们需要求两个字符串中的本质不同并且相同的子串总数。
由于 $n<=3000$
不难发现 $O(n^2)$ 就能过了。
考虑枚举其中一个串的本质不同的所有子串，对于另一个字符串同步匹配。
具体来说，对 $T2$ 串建一个 $SAM$ 。
我们走 $SAM$ 的时候，对于第一个串 $T1$ ，同步行进，找最靠左的的与 $SAM$ 中走过的串完全相等的位置即可。
这里可以用子序列自动机实现。
因为根据贪心找到最左侧的相等字符串对于后续匹配显然更优。
给出代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=3010;
struct SAM{
    int next[27];
    int len,link;
}t[N+N];
int n;
int Next[N+N][27],last,tot;
char A[N+N],B[N+N];
struct Edge{
    int next,to,ty;
}edge[N*4*27];
int sum_edge,head[N+N];
int ans=0;

inline void add_edge(int from,int to,int ty)
{
    ++sum_edge;
    edge[sum_edge].to=to;
    edge[sum_edge].next=head[from];
    edge[sum_edge].ty=ty;
    head[from]=sum_edge;
}
inline void SAM_init()
{
    t[0].link=-1;
    last=0;
}
inline void Insert(int c)
{
    int cur=++tot;
    t[cur].len=t[last].len+1;
    int p=last;
    while(p!=-1 && !t[p].next[c]){
        t[p].next[c]=cur;
        p=t[p].link;
    }
    if(p==-1){
        t[cur].link=0;
        last=cur;
        return ;
    }
    int q=t[p].next[c];
    if(t[p].len+1==t[q].len){
        t[cur].link=q;
        last=cur;
        return ;
    }
    int clone=++tot;
    t[clone].len=t[p].len+1;
    t[clone].link=t[q].link;
    for(register int i=0;i<26;++i)
        t[clone].next[i]=t[q].next[i];
    while(p!=-1 && t[p].next[c]==q){
        t[p].next[c]=clone;
        p=t[p].link;
    }
    t[cur].link=t[q].link=clone;
    last=cur;
    return ;
}
inline void Build()
{
    for(register int i=n;i>=1;--i){
        for(register int j=0;j<26;++j) Next[i-1][j]=Next[i][j];
        Next[i-1][A[i]-'a']=i;
    }
}
inline void dfs(int u,int pos)
{
    for(register int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(Next[pos][edge[i].ty]){
            ++ans;
            dfs(v,Next[pos][edge[i].ty]);
        }
    }
}
int main()
{
    scanf("%d",&n);
    scanf("%s%s",A+1,B+1);
    SAM_init();
    for(register int i=1;i<=n;++i) Insert(B[i]-'a');
    for(register int i=0;i<=tot;++i)
        for(register int k=0;k<26;++k){
            if(t[i].next[k])
                add_edge(i,t[i].next[k],k);
        }
    Build();
    dfs(0,0);
    printf("%d\n",ans);
    return 0;
}