大致题意:
给出一个长度为n的字符串,再给出一个数字k。求出现至少k次的子串中长度最大是多少,注:可覆盖。
大致思路:
后缀数组+二分判定……水水。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax =1000012;
int num[nMax];
int sa[nMax], rank[nMax], height[nMax];
int wa[nMax], wb[nMax], wv[nMax], wd[nMax];
int cmp(int *r, int a, int b, int l){
return r[a] == r[b] && r[a+l] == r[b+l];
}
void da(int *r, int n, int m){ // 倍增算法 r为待匹配数组 n为总长度 m为字符范围
int i, j, p, *x = wa, *y = wb, *t;
for(i = 0; i < m; i ++) wd[i] = 0;
for(i = 0; i < n; i ++) wd[x[i]=r[i]] ++;
for(i = 1; i < m; i ++) wd[i] += wd[i-1];
for(i = n-1; i >= 0; i --) sa[-- wd[x[i]]] = i;
for(j = 1, p = 1; p < n; j *= 2, m = p){
for(p = 0, i = n-j; i < n; i ++) y[p ++] = i;
for(i = 0; i < n; i ++) if(sa[i] >= j) y[p ++] = sa[i] - j;
for(i = 0; i < n; i ++) wv[i] = x[y[i]];
for(i = 0; i < m; i ++) wd[i] = 0;
for(i = 0; i < n; i ++) wd[wv[i]] ++;
for(i = 1; i < m; i ++) wd[i] += wd[i-1];
for(i = n-1; i >= 0; i --) sa[-- wd[wv[i]]] = y[i];
for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i ++){
x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p - 1: p ++;
}
}
}
void calHeight(int *r, int n){ // 求height数组。
int i, j, k = 0;
for(i = 1; i <= n; i ++) rank[sa[i]] = i;
for(i = 0; i < n; height[rank[i ++]] = k){
for(k ? k -- : 0, j = sa[rank[i]-1]; r[i+k] == r[j+k]; k ++);
}
}
int loc[nMax],m;
char str[nMax],res[nMax];
bool vis[1004];
int abs(int a){if(a>0)return a;return -a;}
bool check(int mid,int len,int k){ //长度为mid的子串是否出现了k次
int i,j,tot=0;
for(i=2;i<=len;i++){
if(height[i]<mid)tot=0;
else{
tot++;
if(tot==k-1)return 1;
}
}
return 0;
}
int main(){
int i,j,n,ans,k;
while(scanf("%d%d",&n,&k)!=EOF){
ans=0;
for(i=0;i<n;i++){
scanf("%d",&num[i]);
num[i]++;
}
num[n]=0;
da(num,n+1,1000002);
calHeight(num,n);
int left=0,right=n,mid;//开始二分
while(right>=left){
mid=(right+left)/2;
if(check(mid,n,k)){
left=mid+1;
ans=mid;
}
else{
right=mid-1;
}
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
只是poj上的一条题目,对于理解后缀数组很有帮助.poj3261
NULL 博文链接:https://128kj.iteye.com/blog/1744222
NULL 博文链接:https://128kj.iteye.com/blog/1757060
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1754756
NULL 博文链接:https://128kj.iteye.com/blog/1746750
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
这是西北工业大学的POJ试题的答案,欢迎下载!
NULL 博文链接:https://128kj.iteye.com/blog/1747400
网上整理的一些poj刷题指南。 poj地址:http://poj.org
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
NULL 博文链接:https://128kj.iteye.com/blog/1745671
twilight-poj-solutionPOJ () solution by twilight想当年要找一题的分析, 解答实在太难了现在都是开源的时代了, 干脆把Archive放到GitHub上, 供后来人参考.POJ ID: 部分题解: 转载请注明出处~
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
leetcode 2 和 c 实践 C++ ###数据结构和算法 大批 加一: # 合并排序数组:# 排序 搜索 二分查找:代码、#、#、# 选择 数组中第 K 个最大元素:# 递归 ...动态规划:LeetCode#xx、POJ#xx 后缀数组
POJ 3267 POJ 1260 POJ 1015 POJ 3176 POJ 1080 POJ 1159 POJ 2533 POJ 1836 Leetcode 70 Leetcode 309 搜索 DFS POJ 2488 POJ 3083 POJ 3009 POJ 1321 BFS POJ 3278 POJ 1426 POJ 3126 POJ 3414 POJ 2251 简单搜索...
在程序设计语言中,可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式(又称逆波兰表示法),并最终变为计算机可以直接执行的指令,得到表达式的值。 给定一个中缀表达式,编写程序,利用堆栈的方法,计算...
poj上的题,音乐主题,首先需要对给定的数组差分,之后就是用后缀数组就行
poj 算法题在poj.org上做的一些算法题poj.org 账号:xxfeixiang题目地址:例如,第1001题的地址为:
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...