题目链接:poj 3693 Maximum repetition substring
题目大意:求一个字符串中循环子串次数最多的子串。
解题思路:对字符串构建后缀数组,然后枚举循环长度,分区间确定。对于一个长度l,每次求出i和i+l的LCP,那么以i为起点,循环子串长度为l的子串的循环次数为LCP/l+1,然后再考虑一下从i-l+1~i之间有没有存在增长的可能性。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 100005;
struct Suffix_Arr {
int n, s[maxn];
int SA[maxn], rank[maxn], height[maxn];
int tmp_one[maxn], tmp_two[maxn], c[305];
int d[maxn][20];
void init(char* str);
void build(int m);
void get_height();
void rmq_init();
int rmq_query(int x, int y);
void solve();
}AC;
char str[maxn];
int main () {
int cas = 0;
while (scanf("%s", str) == 1 && strcmp(str, "#")) {
AC.init(str);
AC.build(27);
AC.get_height();
printf("Case %d: ", ++cas);
AC.solve();
}
return 0;
}
void Suffix_Arr::init(char* str) {
n = 0;
int len = strlen(str);
for (int i = 0; i < len; i++)
s[n++] = str[i] - 'a' + 1;
s[n++] = 0;
}
void Suffix_Arr::solve() {
rmq_init();
int ans = 0;
vector<int> vec;
for (int l = 1; l < n; l++) {
for (int i = 0; i + l < n; i += l) {
int lcp = rmq_query(rank[i], rank[i + l]);
int k = lcp / l + 1;
int p = i - (l - lcp % l);
if (p >= 0 && lcp % l && rmq_query(rank[p], rank[p + l]) >= lcp)
k++;
if (k > ans) {
ans = k;
vec.clear();
}
if (k == ans)
vec.push_back(l);
}
}
int pos, len;
for (int i = 0; i < n; i++) {
bool flag = false;
for (int j = 0; j < vec.size(); j++) {
if (SA[i] + vec[j] >= n)
continue;
if (rmq_query(i, rank[SA[i] + vec[j]]) >= (ans - 1) * vec[j]) {
pos = SA[i];
len = vec[j] * ans;
flag = true;
break;
}
}
if (flag)
break;
}
for (int i = 0; i < len; i++)
printf("%c", s[pos + i] + 'a' - 1);
printf("\n");
}
void Suffix_Arr::rmq_init() {
for (int i = 0; i < n; i++) d[i][0] = height[i];
for (int k = 1; (1<<k) <= n; k++) {
for (int i = 0; i + (1<<k) - 1 < n; i++)
d[i][k] = min(d[i][k-1], d[i+(1<<(k-1))][k-1]);
}
}
int Suffix_Arr::rmq_query(int x, int y) {
if (x == y)
return d[x][0];
if (x > y)
swap(x, y);
x++;
int k = 0;
while ((1<<(k+1) <= y - x + 1)) k++;
return min(d[x][k], d[y - (1<<k) + 1][k]);
}
void Suffix_Arr::get_height() {
for (int i = 0; i < n; i++)
rank[SA[i]] = i;
int mv = height[n-1] = 0;
for (int i = 0; i < n - 1; i++) {
if (mv) mv--;
int j = SA[rank[i] - 1];
while (s[i+mv] == s[j+mv])
mv++;
height[rank[i]] = mv;
}
}
void Suffix_Arr::build (int m) {
int *x = tmp_one, *y = tmp_two;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
for (int i = 1; i < m; i++) c[i] += c[i-1];
for (int i = n - 1; i >= 0; i--) SA[--c[x[i]]] = i;
for (int k = 1; k <= n; k <<= 1) {
int mv = 0;
for (int i = n - k; i < n; i++) y[mv++] = i;
for (int i = 0; i < n; i++) if (SA[i] >= k)
y[mv++] = SA[i] - k;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[y[i]]]++;
for (int i = 1; i < m; i++) c[i] += c[i-1];
for (int i = n - 1; i >= 0; i--) SA[--c[x[y[i]]]] = y[i];
swap(x, y);
mv = 1;
x[SA[0]] = 0;
for (int i = 1; i < n; i++)
x[SA[i]] = (y[SA[i-1]] == y[SA[i]] && y[SA[i-1] + k] == y[SA[i] + k] ? mv - 1 : mv++);
if (mv >= n)
break;
m = mv;
}
}
分享到:
相关推荐
poj2479代码 Maximum sum 对于这道题,我的思路是先从左到右,计算并存储每个节点
NULL 博文链接:https://128kj.iteye.com/blog/1744222
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
只是poj上的一条题目,对于理解后缀数组很有帮助.poj3261
西工大POJ习题第五季,数组这类的代码,有截图
在程序设计语言中,可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式(又称逆波兰表示法),并最终变为计算机可以直接执行的指令,得到表达式的值。 给定一个中缀表达式,编写程序,利用堆栈的方法,计算...
poj上的题,音乐主题,首先需要对给定的数组差分,之后就是用后缀数组就行
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ初级-图算法 解题报告+AC代码
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
NULL 博文链接:https://128kj.iteye.com/blog/1757060
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1747400
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
NULL 博文链接:https://128kj.iteye.com/blog/1745671
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告