HihoCoder - 1419 后缀数组四·重复旋律4
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品中的旋律有重复的部分。
我们把一段旋律称为(k,l)-重复的，如果它满足由一个长度为l的字符串重复了k次组成。 如旋律abaabaabaaba是(4,3)重复的，因为它由aba重复4次组成。
小Hi想知道一部作品中k最大的(k,l)-重复旋律。
输入
一行一个仅包含小写字母的字符串。字符串长度不超过 100000。
输出
一行一个整数，表示答案k。
- 样例输入
- babbabaabaabaabab
- 样例输出
- 4
- 总结：
- 首先想到的暴力便是枚举长度l和起始位置i 复杂度O（n * n）
- 然后其实我们可以枚举位置时只枚举l的倍数
- 假设枚举到一个位置i
- 我们需要求出lcp(i, i + l)
- 然后当前的k就为 lcp(i, i + l) / l + 1;
- 但是当前k是偏小的
- 如图 红色加蓝色部分为lcp(i, i + l)
- 蓝色部分为lcp(i, i + l) % l 即为非循环节
- 我们需要向前找到另一部分l – lcp(i, i + l) % l（绿色部分）与其凑成整块
- 然后求lcp(i – (l – lcp(i, i + l) % l, i + l – l + lcp(i, i + l) % l)
- 即求lcp(i – l + lcp(i, i + l) % l, i + lcp(i, i + l) % l) = p
- 然后现在的k1 = p / l + 1; 最后与k取最大值就好
- 求lcp要用到st表 总复杂度O（nlogn）
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int sa[maxn], p, k, ln, y[maxn], rk[maxn], n, m;
int wr[maxn], H[maxn], c[maxn]; char ch[maxn];
int st[maxn][20], Log[maxn], L;
void SA(int x) {
m = x;
for (int i = 1; i <= L; ++i) rk[i] = ch[i];
for (int i = 1; i <= L; ++i) c[rk[i]]++;
for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
for (int i = L; i >= 1; --i) sa[c[rk[i]]--] = i;
p = 0; ln = 1;
while(p < L) {
k = 0;
for (int i = L - ln + 1; i <= L; ++i) y[++k] = i;
for (int i = 1; i <= L; ++i) if(sa[i] > ln) y[++k] = sa[i] - ln;
memset(c, 0, sizeof c);
for (int i = 1; i <= L; ++i) wr[i] = rk[i];
for (int i = 1; i <= L; ++i) c[wr[y[i]]]++;
for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
for (int i = L; i >= 1; --i) sa[c[wr[y[i]]]--] = y[i];
for (int i = 1; i <= L; ++i) wr[i] = rk[i];
rk[sa[1]] = 1; p = 1;
for (int i = 2; i <= L; ++i) {
if(!(wr[sa[i]] == wr[sa[i - 1]] && wr[sa[i] + ln] == wr[sa[i - 1] + ln])) ++p;
rk[sa[i]] = p;
} m = p; ln <<= 1;
}
}
void GH() {
k = 0;
for (int i = 1; i <= L; ++i) rk[sa[i]] = i;
for (int i = 1; i <= L; ++i) {
if(k) --k; int j = sa[rk[i] - 1];
while(ch[i + k] == ch[j + k]) ++k;
H[rk[i]] = k;
}
}
int lcp(int p1, int p2) {
if(rk[p1] > rk[p2]) swap(p1, p2);
p1 = rk[p1]; p2 = rk[p2]; p1++;
int l = Log[p2 - p1 + 1];
return min(st[p1][l], st[p2 - (1 << l) + 1][l]);
}
int main() {
for (int i = 1; i < maxn; ++i) Log[i] = log2(i);
scanf("%s", ch + 1); L = strlen(ch + 1);
SA(256); GH(); int ans = 0;
for (int i = 1; i <= L; ++i) st[i][0] = H[i];
for (int i = 1; i <= 18; ++i) {
for (int j = 1; j <= L; ++j) {
if(j + (1 << i) <= L)
st[j][i] = min(st[j][i - 1], st[j + (1 << i)][i - 1]);
}
}
for (int l = 1; l <= L; ++l) {
for (int i = 1; i + l <= L; i += l) {
int r = lcp(i, i + l);
ans = max(ans, r / l + 1);
if(i >= l - r % l) ans = max(ans, lcp(i - l + r % l, i + r % l) / l + 1);
}
} printf("%d\n", ans);
return 0;
}
版权声明：本文为oi-forever原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。