hdu 4416 Good Article Good sentence (后缀自动机)
http://acm.hdu.edu.cn/showproblem.php?pid=4416
题意：
给出一个字符串A和n个字符串B,问A的子串中，不在任何一个B中出现的本质不同的子串有多少。
思路：
还是根据len搞事情
我们知道，如果不加任何条件，SAM中一个节点所表示的本质不同的子串数量是st[i].len - st[st[i].link].len
现在加了限制条件。
那么该状态中，有一些长度的字符串就会不满足条件。
我们考虑对母串A构建SAM
那么只需要维护B的所有串，对于某个状态能匹配的最大长度，设为maxlen,那么 长度为[maxlen+1,st[i].len]的字符串可以贡献答案。
如果maxlen为0，则该状态所表示的所有本质不同的子串都可以贡献答案。
维护最大匹配长度 可以参考 spoj-lcs2 解题报告
有所不同的是不需要在每一个B中都匹配，只需要至少一个匹配就行了，因此是取所有串的最大匹配长度即可。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月08日 星期三 18时50分18秒
4File Name :4416.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
8#define PB push_back
9#define fst first
10#define sec second
11#define lson l,m,rt<<1
12#define rson m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23#define MAXALP 30
24const int mod = 2012;
25struct state
26{
27 int len, link, nxt[MAXALP];
28};
29const int N =1E5+7;
30state st[N*2];
31int sz, last,rt;
32char s[N];
33int cnt[2*N],rk[2*N];//for radix sort
34int dp[2*N];
35void sa_init()
36{
37 sz = 0;
38 last = rt = ++sz;
39 st[1].len = 0;
40 st[1].link=-1;
41 ms(st[1].nxt,-1);
42}
43void sa_extend(int c)
44{
45 int cur = ++sz;
46 st[cur].len = st[last].len + 1;
47 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
48 int p;
49 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
50 st[p].nxt[c] = cur;
51 if (p == -1) {
52 st[cur].link = rt;
53 } else {
54 int q = st[p].nxt[c];
55 if (st[p].len + 1 == st[q].len) {
56 st[cur].link = q;
57 } else {
58 int clone = ++sz ;
59 st[clone].len = st[p].len + 1;
60 st[clone].link = st[q].link;
61 memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
62 for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
63 st[p].nxt[c] = clone;
64 st[q].link = st[cur].link = clone;
65 }
66 }
67 last = cur;
68}
69void topo()
70{
71 ms(cnt,0);
72 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
73 for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
74 for (int i = 1 ; i <= sz ;i++) rk[cnt[st[i].len]--] = i;
75}
76char ST[N];
77int n;
78int main()
79{
80#ifndef ONLINE_JUDGE
81 freopen("./in.txt","r",stdin);
82#endif
83
84 int T;
85 int cas = 0 ;
86 cin>>T;
87 while (T--)
88 {
89 scanf("%d",&n);
90 scanf("%s",ST);
91 sa_init();
92 for (int i = 0,len = strlen(ST); i < len ; i++)
93 {
94 sa_extend(ST[i]-'a');
95 }
96 topo();
97 ms(dp,0);
98 for ( int i = 0 ; i < n ; i++)
99 {
100 scanf("%s",ST);
101 int now = rt,len = 0;
102 for ( int i = 0,_len = strlen(ST) ; i < _len ; i++)
103 {
104 if (st[now].nxt[ST[i]-'a']!=-1)
105 {
106 now = st[now].nxt[ST[i]-'a'];
107 len++;
108 dp[now] = max(dp[now],len);
109 // printf("now:%d dp[now]:%d len: %d\n",now,dp[now],len);
110 }
111 else
112 {
113 while (now!=-1&&st[now].nxt[ST[i]-'a']==-1) now = st[now].link;
114 if (now==-1) now=rt,len=0;else len = st[now].len + 1,now=st[now].nxt[ST[i]-'a'],dp[now] = max(dp[now],len);
115 }
116 }
117 }
118 LL ans = 0 ;
119 for ( int i = sz ; i >= 1 ; i-- )
120 {
121 int v = rk[i];
122 if (dp[v])
123 {
124 dp[st[v].link] = max(dp[st[v].link],dp[v]);
125 if (dp[v]<st[v].len) ans += st[v].len-dp[v]; // 长度为[dp[v]+1,st[v].len]的串不在n个B串中出现，可以贡献答案。
126 }else ans += st[v].len - st[st[v].link].len;
127 }
128 printf("Case %d: %lld\n",++cas,ans);
129 }
130
131
132
133
134
135#ifndef ONLINE_JUDGE
136 fclose(stdin);
137#endif
138 return 0;
139}