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
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月08日 星期三 18时50分18秒
4File Name :3518.cpp
5************************************************ */
6
7//#include <bits/stdc++.h>
8#include <cstring>
9#include <string>
10#include <algorithm>
11#include <iostream>
12#include <cstdio>
13#include <cmath>
14#define PB push_back
15#define fst first
16#define sec second
17#define lson l,m,rt<<1
18#define rson m+1,r,rt<<1|1
19#define ms(a,x) memset(a,x,sizeof(a))
20typedef long long LL;
21#define pi pair < int ,int >
22#define MP make_pair
23
24using namespace std;
25const double eps = 1E-8;
26const int dx4[4]={1,0,0,-1};
27const int dy4[4]={0,-1,1,0};
28const int inf = 0x3f3f3f3f;
29#define MAXALP 55 //还有大写字母orz
30int k;
31struct state
32{
33 int len, link, nxt[MAXALP];
34};
35const int N =1E5+7;
36state st[N*2];
37int sz, last,rt;
38char s[N];
39int Right[2*N];
40int cnt[2*N],rk[2*N];//for radix sort
41int dp[2*N],lazy[2*N];
42void sa_init()
43{
44 sz = 0;
45 last = rt = ++sz;
46 st[1].len = 0;
47 st[1].link=-1;
48 ms(st[1].nxt,-1);
49}
50void sa_extend(int c)
51{
52 int cur = ++sz;
53 st[cur].len = st[last].len + 1;
54 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
55 int p;
56 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
57 st[p].nxt[c] = cur;
58 if (p == -1) {
59 st[cur].link = rt;
60 } else {
61 int q = st[p].nxt[c];
62 if (st[p].len + 1 == st[q].len) {
63 st[cur].link = q;
64 } else {
65 int clone = ++sz ;
66 st[clone].len = st[p].len + 1;
67 st[clone].link = st[q].link;
68 memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
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 ST[N];
84int idx( char c)
85{
86 if (c>='a'&&c<='z') return c-'a';
87 return c-'A'+26;
88}
89int main()
90{
91#ifndef ONLINE_JUDGE
92 freopen("./in.txt","r",stdin);
93#endif
94 while (~scanf("%d",&k)!=EOF)
95 {
96 if (k==0) break;
97 ms(Right,0);
98 ms(lazy,0); //parent树上的lazy标记，最后子底向上更新
99 scanf("%s",ST);
100// cout<<"ST:"<<ST<<endl;
101 sa_init();
102 for (int i = 0,len = strlen(ST); i < len ; i++)
103 {
104 Right[sz+1] = 1;
105 sa_extend(idx(ST[i]));
106 }
107 topo();
108 for ( int i = sz ; i >=1 ; i--) if (st[rk[i]].link!=-1)Right[st[rk[i]].link]+=Right[rk[i]];
109 //check right
110// for ( int i = sz ; i >=1 ; i--) printf("right:%d\n",Right[i]);
111 scanf("%s",ST);
112 int now = rt,len = 0;
113 LL ans = 0 ;
114 for ( int i = 0,_len = strlen(ST) ; i < _len ; i++)
115 {
116 int id = idx(ST[i]);
117 if (st[now].nxt[id]!=-1)
118 {
119 now = st[now].nxt[id];
120 len++;
121 // printf("now:%d dp[now]:%d len: %d\n",now,dp[now],len);
122 }
123 else
124 {
125 while (now!=-1&&st[now].nxt[id]==-1) now = st[now].link;
126 if (now==-1) now=rt,len=0;else len = st[now].len + 1,now=st[now].nxt[id];
127 }
128// printf("len:%d\n",len);
129 if (len>=k)
130 {
131 if (st[now].link==-1) continue;
132 ans += 1LL*(len-max(k,st[st[now].link].len+1)+1)*Right[now];
133 if (st[st[now].link].len>=k) lazy[st[now].link]++;
134 }
135 }
136
137 for ( int i = sz ; i >= 1 ; i-- )
138 {
139 int v = rk[i];
140 if (st[v].link==-1) continue;
141 ans += 1LL*lazy[v]*(st[v].len-max(k,st[st[v].link].len+1)+1)*Right[v];
142 if (st[st[v].link].len>=k) lazy[st[v].link] += lazy[v]; //lazy标记沿着parent树向上传递
143 }
144 printf("%lld\n",ans);
145 }
146
147
148
149
150
151#ifndef ONLINE_JUDGE
152 fclose(stdin);
153#endif
154 return 0;
155}