【UOJ 219】【BZOJ 4650】【NOI 2016】优秀的拆分(后缀数组)

Description

click me

Solution

2.1

先考虑找到所有形如AA的串的位置:
枚举长度$len$,找到关键点$len$,$2len$,$3len$$\cdots$
发现所有长度为$len$的A的AA串都经过了其中两个关键点。
令$l=k\times len$,$r=(k+1)j\times len$,求以$l$和$r$结尾的串的最长公共后缀长度$x$,以它们开头的最长公共前缀长度$y$,则如果$x+y-1\ge len$,那么可以计入贡献。计入贡献的时候用差分比较方便。

2.2

用上面的方法得到以每个位置开头的AA方案数$ed_i$,以其结束的方案数$st_i$,那么答案等于$\sum st_i ed_{i+1}$

另外,题目有多组数据,名词数组记得清零。

Source

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/****************************
* Au: Hany01
* Prob: uoj219 & bzoj4650 & noi2016
* Date: Jan 31st, 2018
* Email: hany01@foxmail.com
****************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define rep(i , j) for (int i = 0 , i##_end_ = j; i < i##_end_ ; ++ i)
#define For(i , j , k) for (int i = (j) , i##_end_ = (k) ; i <= i##_end_ ; ++ i)
#define Fordown(i , j , k) for (int i = (j) , i##_end_ = (k) ; i >= i##_end_ ; -- i)
#define Set(a , b) memset(a , b , sizeof(a))
#define SZ(a) ((int)(a.size()))
#define ALL(a) a.begin(), a.end()
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define y1 wozenmezhemecaia
#ifdef hany01
#define debug(...) fprintf(stderr , __VA_ARGS__)
#else
#define debug(...)
#endif
inline void File() {
#ifdef hany01
freopen("uoj219.in" , "r" , stdin);
freopen("uoj219.out" , "w" , stdout);
#endif
}
template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
inline int read() {
register char c_; register int _ , __;
for (_ = 0 , __ = 1 , c_ = getchar() ; !isdigit(c_) ; c_ = getchar()) if (c_ == '-') __ = -1;
for ( ; isdigit(c_) ; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
return _ * __;
}
const int maxn = 30005, logmaxn = 17;
int n, c[maxn] , tp[maxn], m, suf[maxn], pre[maxn], Log[maxn];
LL Ans;
char s[maxn];
struct Suffix_Array
{
int sa[maxn], height[maxn], Min[maxn][logmaxn], tmp, rk[maxn];
inline void Radix_Sort()
{
For(i, 1, m) c[i] = 0;
For(i, 1, n) ++ c[rk[i]];
For(i, 1, m) c[i] += c[i - 1];
Fordown(i, n, 1) sa[c[rk[tp[i]]] --] = tp[i];
}
inline void Build_SA(char *s)
{
Set(rk, 0);
For(i, 1, n) rk[i] = s[i], tp[i] = i;
m = 255, Radix_Sort();
for (register int k = 1, p = 0; k <= n; k <<= 1, p = 0) {
For(i, n - k + 1, n) tp[++ p] = i;
For(i, 1, n) if (sa[i] > k) tp[++ p] = sa[i] - k;
Radix_Sort(); swap(rk, tp);
rk[sa[1]] = 1, m = 1;
For(i, 2, n) rk[sa[i]] = tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + k] == tp[sa[i - 1] + k] ? m : ++ m;
if (m == n) break;
}
for (register int i = 1, j, k = 0; i <= n; height[rk[i ++]] = k)
for (k = k ? k - 1 : 0, j = sa[rk[i] - 1]; s[i + k] == s[j + k]; ++ k) ;
}
inline void ST_Init()
{
For(i, 1, n) Min[i][0] = height[i];
for (register int j = 1; (1 << j) <= n; ++ j)
For(i, 1, n - (1 << j) + 1) Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);
}
inline int ST_Query(int l, int r)
{
l = rk[l], r = rk[r]; if (l > r) swap(l, r); ++ l;
tmp = Log[r - l + 1];
return min(Min[l][tmp], Min[r - (1 << tmp) + 1][tmp]);
}
}A, B;
int main()
{
File();
For(i, 2, maxn - 5) Log[i] = Log[i >> 1] + 1;
for (register int T = read(); T --; ) {
scanf("%s", s + 1), n = strlen(s + 1);
A.Build_SA(s), reverse(s + 1, s + 1 + n), B.Build_SA(s);
reverse(B.rk + 1, B.rk + n + 1);
A.ST_Init(), B.ST_Init();
Set(pre, 0), Set(suf, 0);
For(len, 1, n >> 1)
for (register int l = len, r = l + len, x, y; r <= n; l = r, r += len) {
chkmin(x = A.ST_Query(l, r), len), chkmin(y = B.ST_Query(l, r), len);
if (x + y - 1 < len) continue;
++ pre[l - y + 1], -- pre[l + x - len + 1],
++ suf[r - y + len], -- suf[r + x];
}
For(i, 1, n) pre[i] += pre[i - 1], suf[i] += suf[i - 1];
Ans = 0;
For(i, 1, n - 1) Ans += pre[i + 1] * 1ll * suf[i];
cout << Ans << endl;
}
return 0;
}
Contents
  1. 1. Description
  2. 2. Solution
    1. 2.1. 2.1
    2. 2.2. 2.2
  3. 3. Source