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

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define N (220009)
 5 #define LL unsigned long long
 6 using namespace std;
 7 
 8 int T;
 9 LL f1[N],f2[N];
10 char s[N],t[N];
11 
12 struct SAM
13 {
14     int son[N][28],fa[N],step[N];
15     int p,q,np,nq,last,cnt;
16     SAM(){last=cnt=1;}
17     void clear()
18     {
19         last=cnt=1;
20         memset(son,0,sizeof(son));
21         memset(fa,0,sizeof(fa));
22         memset(step,0,sizeof(step));
23     }
24     void Insert(int x)
25     {
26         p=last; np=last=++cnt; step[np]=step[p]+1;
27         while (p && !son[p][x]) son[p][x]=np,p=fa[p];
28         if (!p) fa[np]=1;
29         else
30         {
31             q=son[p][x];
32             if (step[q]==step[p]+1) fa[np]=q;
33             else
34             {
35                 nq=++cnt; step[nq]=step[p]+1;
36                 memcpy(son[nq],son[q],sizeof(son[q]));
37                 fa[nq]=fa[q]; fa[q]=fa[np]=nq;
38                 while (son[p][x]==q) son[p][x]=nq,p=fa[p];
39             }
40         }
41     }
42 }SAM[2];
43 
44 LL DFS2(int x)
45 {
46     if (!x) return 0;
47     if (f2[x]) return f2[x];
48     f2[x]=1;
49     for (int i=0; i<26; ++i)
50     {
51         LL nxt=SAM[1].son[x][i];
52         if (nxt) f2[x]+=DFS2(nxt);
53     }
54     return f2[x];
55 }
56 
57 LL DFS1(int x)
58 {
59     if (f1[x]) return f1[x];
60     f1[x]=1;
61     for (int i=0; i<26; ++i)
62     {
63         LL nxt=SAM[0].son[x][i];
64         if (nxt) f1[x]+=DFS1(nxt);
65         else f1[x]+=DFS2(SAM[1].son[1][i]);
66     }
67     return f1[x];
68 }
69 
70 int main()
71 {
72     scanf("%d",&T);
73     while (T--)
74     {
75         memset(f1,0,sizeof(f1));
76         memset(f2,0,sizeof(f2));
77         SAM[0].clear(); SAM[1].clear();
78         scanf("%s%s",s,t);
79         for (int i=0,l=strlen(s); i<l; ++i)
80             SAM[0].Insert(s[i]-'a');
81         for (int i=0,l=strlen(t); i<l; ++i)
82             SAM[1].Insert(t[i]-'a');
83         printf("%llu
",DFS1(1));
84     }
85 }