F - Repeats SPOJ - REPEATS

这是一篇论文里面的题目，虽然看了论文里面的解法，发现对我还是比较难理解，最后思考了好久才明白这题的具体做法。
我们去枚举重复子串的长度，如果这个子串的重复长度大于等于2，那么对每个枚举的长度L来说，我们计算S[0], S[L], S[2*L], S[3*L]……，这些相邻的两个后缀，一定会有一个大于L的前缀(也有可能在当前的前面），设这个前缀为k那么长为L的串就会重复k/L+1次，同时要考虑前面有没有可能有多余的没有匹配上的，比如ebbbb对于L=2时，bbb与b的前缀只有1，是因为没有考虑到前面的一位，所以要再往前处理下。

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define Max_N (2*50000 + 100)
int n;
int k;
int a[Max_N];
int rank1[Max_N];
int tmp[Max_N];
bool compare_sa(int i, int j)
{
if(rank1[i] != rank1[j]) return rank1[i] < rank1[j];
else {
int ri = i + k <= n ? rank1[i + k] : -1;
int rj = j + k <= n ? rank1[j + k] : -1;
return ri < rj;
}
}
void construct_sa(int buf[], int s, int sa[])
{
int len = s;
for (int i = 0; i <= len; i++) {
sa[i] = i;
rank1[i] = i < len ? buf[i] : -1;
}
for ( k = 1; k <= len; k *= 2) {
sort(sa, sa + len +1, compare_sa);
tmp[sa[0]] = 0;
for (int i = 1; i <= len; i++) {
tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
}
for (int i = 0; i <= len; i++) {
rank1[i] = tmp[i];
}
}
}
void construct_lcp(int buf[], int len, int *sa, int *lcp)
{
int h = 0;
lcp[0] = 0;
for (int i = 0; i < len; i++) {
int j = sa[rank1[i] - 1];
if (h > 0) h--;
for (; j + h < len && i + h < len; h++) {
if (buf[j+h] != buf[i+h]) break;
}
lcp[rank1[i] - 1] = h;
}
}
int sa[Max_N];
int rev[Max_N];
int lcp[Max_N];
char str[3];
int f[Max_N][20];
void rmq()
{
for (int i = 1; i <= n; i++)
f[i][0] = lcp[i];
f[n][0] = 1000000;
for (int j=1; (1<<j) <= n ; j++)
for (int i=1; i+(1<<j)-1<=n; i++)
f[i][j]= min(f[i][j-1],f[i+(1<<j-1)][j-1]);
return;
}
int lcp1(int L, int R)
{
if (L> R) {
int ss = R;
R = L;
L = ss;
}
R--;
int k1 = 0;
while((1<<(k1+1)) <= R-L+1) k1++;
return min(f[L][k1], f[R-(1<<k1)+1][k1]);
}
int main()
{
int T;
cin >> T;
while (T--) {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%s", str);
a[i] = int(str[0]);
}
a[n] = 0;
construct_sa(a, n, sa);
construct_lcp(a, n, sa, lcp);
rmq();
/*int l,r;
cin >> l >> r;
cout << lcp1(l, r) << endl;*/
int max = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j + i < n; j += i) {
int k1 = lcp1(rank1[j], rank1[j+i]);
int r = k1 / i + 1;
int t = j - (i - k1%i);
if (t >= 0)
if (lcp1(rank1[t], rank1[t+i]) >= i) r++;
if (r > max) max = r;
}
}
if (max == 0) max = 1;
printf("%dn", max);
}
return 0;
}

最后

以上就是细心河马最近收集整理的关于F - Repeats SPOJ - REPEATS的全部内容，更多相关F内容请搜索靠谱客的其他文章。