HDU5343:MZL's Circle Zhou(SAM,记忆化搜索DP)

Description

Input

Output

Sample Input

Sample Output

Solution

题意：给你两个串，分别从两个里面各选出一个子串拼到一起，问能构成多少个本质不同的字符串。

首先考虑一下，什么时候一个串会被重复计算。

例如假设串$abcad$，可以由$ab+cad$或$a+bcad$组成。

第一个串中可以用$ab$，也可以用$a$。$a$可以构成$abcad$，那么$ab$也能构成$abcad$。

也就是说，我们要在第一个串中找一个最靠右的，然后再到第二个串中找。

具体操作就是，在第一个串的$SAM$上$DFS$，如果字符$c$失配的话，就到第二个串的$SAM$上根的$c$儿子上继续去$DFS$。

这样就可以做到不重不漏了。再加一个记忆化就可以过了。还得开$unsigned~long~long$……

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define N (220009)

 #define LL unsigned long long

 using namespace std;

 int T;

 LL f1[N],f2[N];

 char s[N],t[N];

 struct SAM

 {

     int son[N][],fa[N],step[N];

     int p,q,np,nq,last,cnt;

     SAM(){last=cnt=;}

     void clear()

     {

         last=cnt=;

         memset(son,,sizeof(son));

         memset(fa,,sizeof(fa));

         memset(step,,sizeof(step));

     }

     void Insert(int x)

     {

         p=last; np=last=++cnt; step[np]=step[p]+;

         while (p && !son[p][x]) son[p][x]=np,p=fa[p];

         if (!p) fa[np]=;

         else

         {

             q=son[p][x];

             if (step[q]==step[p]+) fa[np]=q;

             else

             {

                 nq=++cnt; step[nq]=step[p]+;

                 memcpy(son[nq],son[q],sizeof(son[q]));

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

                 while (son[p][x]==q) son[p][x]=nq,p=fa[p];

             }

         }

     }

 }SAM[];

 LL DFS2(int x)

 {

     if (!x) return ;

     if (f2[x]) return f2[x];

     f2[x]=;

     for (int i=; i<; ++i)

     {

         LL nxt=SAM[].son[x][i];

         if (nxt) f2[x]+=DFS2(nxt);

     }

     return f2[x];

 }

 LL DFS1(int x)

 {

     if (f1[x]) return f1[x];

     f1[x]=;

     for (int i=; i<; ++i)

     {

         LL nxt=SAM[].son[x][i];

         if (nxt) f1[x]+=DFS1(nxt);

         else f1[x]+=DFS2(SAM[].son[][i]);

     }

     return f1[x];

 }

 int main()

 {

     scanf("%d",&T);

     while (T--)

     {

         memset(f1,,sizeof(f1));

         memset(f2,,sizeof(f2));

         SAM[].clear(); SAM[].clear();

         scanf("%s%s",s,t);

         for (int i=,l=strlen(s); i<l; ++i)

             SAM[].Insert(s[i]-'a');

         for (int i=,l=strlen(t); i<l; ++i)

             SAM[].Insert(t[i]-'a');

         printf("%llu\n",DFS1());

     }

 }