POJ3415CommonSubstrings（后缀数组）

1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7 typedef long long LL;
8
9 const int MAXN = 200010;
10
11 char s[MAXN];
12 int sa[MAXN], rank[MAXN], height[MAXN], c[MAXN], tmp[MAXN];
13 int n, apart, k;
14
15 void makesa(int m) {
16 memset(c, 0, m * sizeof(int));
17 for(int i = 0; i s[i]];
18 for(int i = 1; i 1];
19 for(int i = 0; i i;
20 for(int k = 1; k 1) {
21 for(int i = 0; i i) {
22 int j = sa[i] - k;
23 if(j <0) j += n;
24 tmp[c[rank[j]]++] = j;
25 }
26 int j = c[0] = sa[tmp[0]] = 0;
27 for(int i = 1; i i) {
28 if(rank[tmp[i]] != rank[tmp[i - 1]] || rank[tmp[i] + k] != rank[tmp[i - 1] + k])
29 c[++j] = i;
30 sa[tmp[i]] = j;
31 }
32 memcpy(rank, sa, n * sizeof(int));
33 memcpy(sa, tmp, n * sizeof(int));
34 }
35 }
36
37 void calheight() {
38 for(int i = 0, k = 0; i k) {
39 k -= (k > 0);
40 int j = sa[rank[i] - 1];
41 while(s[i + k] == s[j + k]) ++k;
42 }
43 }
44
45 struct Node {
46 int height, cnt;
47 Node(int height = 0, int cnt = 0): height(height), cnt(cnt) {}
48 };
49
50 LL solve() {
51 LL ans = 0, sum = 0;
52 stack stk;
53
54 for(int i = 1; i i) {
55 int cnt = 0;
56 while(!stk.empty() && stk.top().height >= height[i]) {
57 Node t = stk.top(); stk.pop();
58 cnt += t.cnt;
59 sum -= t.cnt * (t.height - k + 1LL);
60 }
61 if(height[i] >= k) {
62 cnt += (sa[i - 1] < apart);
63 if(cnt) stk.push(Node(height[i], cnt));
64 sum += cnt * (height[i] - k + 1LL);
65 }
66 if(sa[i] > apart) ans += sum;
67 }
68
69 while(!stk.empty()) stk.pop();
70 sum = 0;
71
72 for(int i = 1; i i) {
73 int cnt = 0;
74 while(!stk.empty() && stk.top().height >= height[i]) {
75 Node t = stk.top(); stk.pop();
76 cnt += t.cnt;
77 sum -= t.cnt * (t.height - k + 1LL);
78 }
79 if(height[i] >= k) {
80 cnt += (sa[i - 1] > apart);
81 stk.push(Node(height[i], cnt));
82 sum += cnt * (height[i] - k + 1LL);
83 }
84 if(sa[i] sum;
85 }
86
87 return ans;
88 }
89
90 int main() {
91 while(scanf("%d", &k) != EOF && k) {
92 scanf("%s", s);
93 apart = strlen(s);
94 s[apart] = ‘$‘;
95 scanf("%s", s + apart + 1);
96 n = strlen(s) + 1;
97 makesa(128);
98 calheight();
99 cout<endl;
100 }
101 }