poj 3415 Common Substrings (后缀自动机+parent树上的lazy标记)
http://poj.org/problem?id=3415
题意：
给出两个字符串，问公共长度大于等于k的子串个数（只要两个串的位置不同就认为是不同）
思路：
考虑SAM的性质。
SAM上的一个节点所能接受的本质不同的子串个数是**st[v].len - st[st[v].link].len**
而这些子串，都出现了right[v]次，因为不同子串的个数就是**(st[v].len-st[st[v].link].len)right[v]*
现在有了限制条件，要求长度大于等于k.
没有限制的话，SAM上的一个节点所能接受的字符串的长度范围是在[st[st[v].link].len+1,st[v].len]
那么现在范围其实就变成了**[MX,st[v].len],其中MX = max{st[st[v].link].len+1,k}**
对于A串构建SAM，然后B串在SAM上运行
考虑对于SAM的某个状态，B串此时的最大匹配长度为len，那么len>=MX时，满足条件的字符串的范围就变成了**[MX,len] **
len<MX时无贡献。
所以该状态(v)对答案的就是 (len-MX+1)*right[v]
然而这还不算完，和之前的LCS2一样，如果SAM上的一个节点能匹配字符串B的长度大于等于k，那么该节点的祖先节点（父亲节点，父亲的父亲的节点...)
能匹配的字符串B的长度也都大于等于k...
如果我们一边匹配一边沿着parent树自底向上传递的话...复杂度n^2,一首凉凉送给自己
但是正常人会这样？.jpg
我们先打个标记，最后沿parent树自底向上把标记传递上去就行了。。
需要注意的是，此题的字符集是大小写字母都会包含...RE了2发orz
/* ***********************************************
Author :111qqz
Created Time :2017年11月08日 星期三 18时50分18秒
File Name :3518.cpp
************************************************ */
1//#include <bits/stdc++.h>
2#include <cstring>
3#include <string>
4#include <algorithm>
5#include <iostream>
6#include <cstdio>
7#include <cmath>
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
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6#define MAXALP 55 //还有大写字母orz
7int k;
8struct state
9{
10 int len, link, nxt[MAXALP];
11};
12const int N =1E5+7;
13state st[N*2];
14int sz, last,rt;
15char s[N];
16int Right[2*N];
17int cnt[2*N],rk[2*N];//for radix sort
18int dp[2*N],lazy[2*N];
19void sa_init()
20{
21 sz = 0;
22 last = rt = ++sz;
23 st[1].len = 0;
24 st[1].link=-1;
25 ms(st[1].nxt,-1);
26}
27void sa_extend(int c)
28{
29 int cur = ++sz;
30 st[cur].len = st[last].len + 1;
31 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
32 int p;
33 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
34 st[p].nxt[c] = cur;
35 if (p == -1) {
36 st[cur].link = rt;
37 } else {
38 int q = st[p].nxt[c];
39 if (st[p].len + 1 == st[q].len) {
40 st[cur].link = q;
41 } else {
42 int clone = ++sz ;
43 st[clone].len = st[p].len + 1;
44 st[clone].link = st[q].link;
45 memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
46 for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
47 st[p].nxt[c] = clone;
48 st[q].link = st[cur].link = clone;
49 }
50 }
51 last = cur;
52}
53void topo()
54{
55 ms(cnt,0);
56 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
57 for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
58 for (int i = 1 ; i <= sz ;i++) rk[cnt[st[i].len]--] = i;
59}
60char ST[N];
61int idx( char c)
62{
63 if (c>='a'&&c<='z') return c-'a';
64 return c-'A'+26;
65}
66int main()
67{
68#ifndef ONLINE_JUDGE
69 freopen("./in.txt","r",stdin);
70#endif
71 while (~scanf("%d",&k)!=EOF)
72 {
73 if (k==0) break;
74 ms(Right,0);
75 ms(lazy,0); //parent树上的lazy标记，最后子底向上更新
76 scanf("%s",ST);
77// cout<<"ST:"<<ST<<endl;
78 sa_init();
79 for (int i = 0,len = strlen(ST); i < len ; i++)
80 {
81 Right[sz+1] = 1;
82 sa_extend(idx(ST[i]));
83 }
84 topo();
85 for ( int i = sz ; i >=1 ; i--) if (st[rk[i]].link!=-1)Right[st[rk[i]].link]+=Right[rk[i]];
86 //check right
87// for ( int i = sz ; i >=1 ; i--) printf("right:%d\n",Right[i]);
88 scanf("%s",ST);
89 int now = rt,len = 0;
90 LL ans = 0 ;
91 for ( int i = 0,_len = strlen(ST) ; i < _len ; i++)
92 {
93 int id = idx(ST[i]);
94 if (st[now].nxt[id]!=-1)
95 {
96 now = st[now].nxt[id];
97 len++;
98 // printf("now:%d dp[now]:%d len: %d\n",now,dp[now],len);
99 }
100 else
101 {
102 while (now!=-1&&st[now].nxt[id]==-1) now = st[now].link;
103 if (now==-1) now=rt,len=0;else len = st[now].len + 1,now=st[now].nxt[id];
104 }
105// printf("len:%d\n",len);
106 if (len>=k)
107 {
108 if (st[now].link==-1) continue;
109 ans += 1LL*(len-max(k,st[st[now].link].len+1)+1)*Right[now];
110 if (st[st[now].link].len>=k) lazy[st[now].link]++;
111 }
112 }
1 for ( int i = sz ; i >= 1 ; i-- )
2 {
3 int v = rk[i];
4 if (st[v].link==-1) continue;
5 ans += 1LL*lazy[v]*(st[v].len-max(k,st[st[v].link].len+1)+1)*Right[v];
6 if (st[st[v].link].len>=k) lazy[st[v].link] += lazy[v]; //lazy标记沿着parent树向上传递
7 }
8 printf("%lld\n",ans);
9 }
1#ifndef ONLINE_JUDGE
2 fclose(stdin);
3#endif
4 return 0;
5}