。

做这种题终于不用写SA+二分/set/单调栈...了。。

\(Description\)

给定两个字符串，求它们有多少个相同子串。相同串的位置不同算多个。

\(Solution\)

对一个串建SAM。因为要统计不同位置个数，所以匹配一个点的贡献为\((val[i]=(len[i]-len[fa[i]])*|right[i]|)+val[fa[i]]+val[fa[fa[i]]]...\)

然后另一个串在SAM上走。维护当前已匹配的长度l，则当前贡献为\(val[fa[i]]+(l-len[fa[i]])*|right[i]|\)。

//52776kb   1500ms#include 
    
     #include 
     
      #include 
      
       #define gc() getchar()typedef long long LL;const int N=4e5+5;struct Suffix_Automaton{    int las,tot,fa[N],son[N][26],len[N],A[N],tm[N],right[N];    LL val[N];    char s[N];    void Insert(int c)    {        int np=++tot,p=las;        len[las=np]=len[p]+1, right[np]=1;        for(; p&&!son[p][c]; p=fa[p]) son[p][c]=np;        if(!p) fa[np]=1;        else        {            int q=son[p][c];            if(len[q]==len[p]+1) fa[np]=q;            else            {                int nq=++tot; len[nq]=len[p]+1;                memcpy(son[nq],son[q],sizeof son[q]);                fa[nq]=fa[q], fa[q]=fa[np]=nq;                for(; son[p][c]==q; p=fa[p]) son[p][c]=nq;            }        }    }    void Build()    {        las=tot=1;        scanf("%s",s); int l=strlen(s);        for(int i=0; i