大致题意:
给出一个数字m和一个字符串str,求出str中至少出现m次的最长的子串长度,并且求出这些子串中最靠右的子串的位置。
大致思路:
先求出后缀数组,二分枚举这个长度mid,然后分析height数组的每个大于mid的区间。过程稍复杂,具体看我代码即可。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=500000;
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,ans;
char str[nMax],res[nMax];
int abs(int a){
if(a>0)return a;
return -a;
}
bool check(int mid,int len){
int i,j,a=0,b=0,c=0,flag=0;
for(i=2;i<=len;i++){
if(height[i]>=mid){
a++;
b=max(sa[i],max(sa[i-1],b));
}
else{
if(a>=m-1){
c=max(b,c);
flag=1;
}
b=0;
a=0;
}
}
if(a>=m-1){
c=max(b,c);
flag=1;
}
if(flag)ans=c;
return flag;
}
int main(){
int n,i,sp,ddd;
while(scanf("%d",&m)!=EOF&&m){
scanf("%s",str);
n=strlen(str);
sp=30;
if(m==1){
printf("%d %d\n",n,0);
continue;
}
for(i=0;str[i];i++){
num[i]=str[i]-'a'+1;
}
num[n]=0;
da(num,n+1,sp+4);
calHeight(num,n);
// cout<<check(3,n)<<" ";
// cout<<ans<<endl;
int left=0,right=n,mid;//开始二分
while(right>=left){
mid=(right+left)/2;
if(check(mid,n)){ //判断长度为mid的串是否重复了m次
left=mid+1;
ddd=mid;
}
else{
right=mid-1;
}
}
//cout<<mid<<endl;
if(ddd){
printf("%d %d\n",ddd,ans);
}
else{
printf("none\n");
}
}
return 0;
}
分享到:
相关推荐
### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...
【标题】:“HDOJ题目分类 HDOJ题目分类” HDOJ,全称为Happy DingO Online Judge,是一个在线编程竞赛平台,它为参赛者提供了大量编程题目进行练习和比赛,旨在提升编程技能和算法理解。HDOJ的题目分类是帮助用户...
【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...
根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...
【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...
《HDOJ离线版:探索编程竞赛的智慧宝库》 HDOJ,全称为“杭州电子科技大学在线评测系统”(Hangzhou Dianzi University Online Judge),是中国早期的编程竞赛平台之一,深受广大编程爱好者和在校学生的喜爱。HDOJ...
"hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...
HDOJ1000.java HDOJ1001.java HDOJ1089.java HDOJ1090.java HDOJ1091.java HDOJ1092.java HDOJ1093.java HDOJ1094.java HDOJ1095.java HDOJ1108.java HDOJ1406.java HDOJ2001.java HDOJ2002.java HDOJ2003.java HDOJ...
hdoj-problem-archive 杭电OJ题目源码记录 —— a source code of hdoj acm problem archive 简介 此项目为 的 题目以及代码仓库 src 中每一个文件夹代表一个题目 每个文件夹中都有 原题文档介绍.md 原题文档介绍.md...
### hdoj杭电入门训练题 #### 概述 杭电在线评测系统(HDOJ)是中国杭州电子科技大学提供的一套在线编程题库平台,主要用于计算机程序设计竞赛(ACM-ICPC)的训练与选拔。对于初学者而言,通过解决HDOJ中的题目可以...
“hdoj 2013 多校训练2标程+解题报告”这个标题指的是2013年举行的一场由hdoj(HDU Online Judge,即杭州电子科技大学在线评测系统)组织的多校联合编程训练活动的第二阶段。其中,“标程”是指官方提供的正确解答...
例如,在解决HDOJ_3068_最长回文子串问题时,Manacher算法能够快速准确地找出给定字符串中的最长回文子串,为各种文本分析、模式匹配等任务提供了高效的解决方案。 综上所述,Manacher算法作为一种专门针对回文子串...
hdoj1001标程
ACM ICPC HDOJ1002
【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...
ACM ICPC HDOJ1001
hdoj1004,解题代码,答案代码,欢迎下载
【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...
【标题】"HDOJ.rar_HD_HDOJ" 是一个与HDU(杭州电子科技大学)在线判题系统HDOJ相关的压缩包文件,其中包含了大量编程题目的源代码。 【描述】提到,这个压缩包包含了几百道HDOJ题目的源代码,这意味着它是一个宝贵...
ACM ICPC HDOJ1003