hdu 3518 Boring counting (后缀自动机)
http://acm.hdu.edu.cn/showproblem.php?pid=3518
题意：
给一个字符串，问字符串中，至少出现2次且不相交的本质不同的子串有多少个。本质不同给的子串是说存在至少一位的字母不同。
思路：
考虑SAM
SAM上的一个节点表示的是一段长度从[st[st[i].link],len+1,st[i].len]的字符串。
考虑其right集合，如果right集合中最大的r设为rightmost,最小的r设为leftmost.
那么如果rightmost-leftmost+1 > st[i].len ，说明什么呢？
说明该状态所表示的最长的字符串能够至少放下两个而不重叠。
即从[leftmost-st[i].len+1,leftmost]一段 和 从[rightmost-st[i].len+1,rightmost]一段。
如果最长的能放下，那么其他的也一定能放下。因此对答案贡献为st[i].len - st[st[i].link].len
如果rightmost-leftmost+1<=st[i].len，也就是rightmost-leftmost<st[i].len
这个时候长的字符串因为重叠了不能出现2次，但是短的字符串仍然可以贡献答案。
考虑如下图：
此时对答案的贡献为rightmost-leftmost+1 - (st[st[i].link].len+1),化简得到rightmost-leftmost-st[st[i].link].len
综合2种情况，SAM中每个节点对答案的贡献是** min(rightmost-leftmost,st[i].len)-st[st[i].link].len**
需要注意的是只有在st[i].link存在并且rightmost-leftmost>st[st[i].link].len 时 才更新答案
leftmost可以在构建的时候直接求出,rightmost用拓扑序更新下即可。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月08日 星期三 18时50分18秒
4File Name :4436.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 int leftmost; //由于要求出现位置最小的，所以维护某个状态的right集合中r值最小的
29 int rightmost;
30};
31const int N =1E3+7;
32state st[N*2];
33int sz, last,rt;
34char s[N];
35int cnt[2*N],rk[2*N];//for radix sort
36void sa_init()
37{
38 sz = 0;
39 last = rt = ++sz;
40 st[1].len = 0;
41 st[1].link=-1;
42 st[1].rightmost=0;
43 ms(st[1].nxt,-1);
44}
45void sa_extend(int c,int head)
46{
47 int cur = ++sz;
48 st[cur].len = st[last].len + 1;
49 st[cur].leftmost = st[cur].rightmost = head;
50 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
51
52 int p;
53 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
54 st[p].nxt[c] = cur;
55 if (p == -1) {
56 st[cur].link = rt;
57 } else {
58 int q = st[p].nxt[c];
59 if (st[p].len + 1 == st[q].len) {
60
61 st[cur].link = q;
62 } else {
63 int clone = ++sz ;
64 st[clone].len = st[p].len + 1;
65 st[clone].link = st[q].link;
66 memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
67 st[clone].leftmost = st[q].leftmost;
68 st[clone].rightmost = st[q].rightmost;
69 for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
70 st[p].nxt[c] = clone;
71 st[q].link = st[cur].link = clone;
72 }
73 }
74 last = cur;
75}
76void topo()
77{
78 ms(cnt,0);
79 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
80 for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
81 for (int i = 1 ; i <= sz ;i++) rk[cnt[st[i].len]--] = i;
82}
83char S[N];
84int main()
85{
86#ifndef ONLINE_JUDGE
87 freopen("./in.txt","r",stdin);
88#endif
89
90 while (~scanf("%s",S))
91 {
92 if (S[0]=='#') break;
93 sa_init();
94 for ( int i = 0,len = strlen(S) ; i < len ; i++)
95 {
96 sa_extend(S[i]-'a',i);
97 }
98
99 topo();
100 for ( int i = sz ; i >=1 ; i--)
101 {
102 int v = rk[i];
103 int fa = st[v].link;
104 st[fa].rightmost = max(st[fa].rightmost,st[v].rightmost);
105// printf("len:%d rightmost %d leftmost:%d\n",st[i].len,st[i].rightmost,st[i].leftmost);
106 }
107
108 LL ans = 0 ;
109 for ( int i = 1 ; i <= sz ; i++) if (st[i].link!=-1&&st[i].rightmost-st[i].leftmost>st[st[i].link].len)
110 ans += min(st[i].len,st[i].rightmost-st[i].leftmost)-st[st[i].link].len;
111 printf("%lld\n",ans);
112 }
113
114
115
116#ifndef ONLINE_JUDGE
117 fclose(stdin);
118#endif
119 return 0;
120}
121
122
123
124
125
126
127
128/* ***********************************************
129Author :111qqz
130Created Time :2017年11月15日 星期三 19时06分15秒
131File Name :SAM.cpp
132************************************************ */
133
134#include <bits/stdc++.h>
135#define PB push_back
136#define fst first
137#define sec second
138#define lson l,m,rt<<1
139#define rson m+1,r,rt<<1|1
140#define ms(a,x) memset(a,x,sizeof(a))
141typedef long long LL;
142#define pi pair < int ,int >
143#define MP make_pair
144
145using namespace std;
146const double eps = 1E-8;
147const int dx4[4]={1,0,0,-1};
148const int dy4[4]={0,-1,1,0};
149const int inf = 0x3f3f3f3f;
150#define MAXALP 30
151const int N=1E3+7;
152struct SAM
153{
154 struct state
155 {
156 int len, link, nxt[MAXALP];
157 int leftmost; //某个状态的right集合中r值最小的
158 int rightmost;//某个状态的right集合的r的最大值
159 int Right; //right集合大小
160 };
161 state st[N*2];
162 char S[N];
163 int sz, last,rt;
164 char s[N];
165 int cnt[2*N],rk[2*N];//for radix sort
166 void init()
167 {
168 sz = 0;
169 last = rt = ++sz;
170 st[1].len = 0;
171 st[1].link=-1;
172 st[1].rightmost=0;
173 ms(st[1].nxt,-1);
174 }
175 void extend(int c,int head)
176 {
177 int cur = ++sz;
178 st[cur].len = st[last].len + 1;
179 st[cur].leftmost = st[cur].rightmost = head;
180 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
181 int p;
182 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
183 st[p].nxt[c] = cur;
184 if (p == -1) {
185 st[cur].link = rt;
186 } else {
187 int q = st[p].nxt[c];
188 if (st[p].len + 1 == st[q].len) {
189
190 st[cur].link = q;
191 } else {
192 int clone = ++sz ;
193 st[clone].len = st[p].len + 1;
194 st[clone].link = st[q].link;
195 memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
196 st[clone].leftmost = st[q].leftmost;
197 st[clone].rightmost = st[q].rightmost;
198 for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
199 st[p].nxt[c] = clone;
200 st[q].link = st[cur].link = clone;
201 }
202 }
203 last = cur;
204 }
205 void topo()
206 {
207 ms(cnt,0);
208 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
209 for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
210 for (int i = 1 ; i <= sz ;i++) rk[cnt[st[i].len]--] = i;
211 }
212 void pre() //跑拓扑序，预处理一些东西
213 {
214 for ( int i = sz ; i >= 2 ; i--)
215 {
216 int v = rk[i];
217 int fa = st[v].link;
218 if (fa==-1) continue;
219 st[fa].rightmost = max(st[fa].rightmost,st[v].rightmost);
220 st[fa].Right += st[v].Right;
221 }
222 }
223 void solve()
224 {
225
226 LL ans = 0 ;
227 for ( int i = 1 ; i <= sz ; i++) if (st[i].link!=-1&&st[i].rightmost-st[i].leftmost>st[st[i].link].len)
228 ans += min(st[i].len,st[i].rightmost-st[i].leftmost)-st[st[i].link].len;
229 printf("%lld\n",ans);
230 }
231}A;
232int main()
233{
234#ifndef ONLINE_JUDGE
235 freopen("./in.txt","r",stdin);
236#endif
237
238 while (~scanf("%s",A.S))
239 {
240 if (A.S[0]=='#') break;
241 A.init();
242 for ( int i = 0,len = strlen(A.S) ; i < len ; i++)
243 {
244 A.extend(A.S[i]-'a',i);
245 }
246 A.topo();
247 A.pre();
248 A.solve();
249 }
250
251
252
253#ifndef ONLINE_JUDGE
254 fclose(stdin);
255#endif
256 return 0;
257}