`
暴风雪
  • 浏览: 387914 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[后缀数组]hdoj 4080:Stammering Aliens

阅读更多

大致题意:

    给出一个数字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;
}
 
0
0
分享到:
评论

相关推荐

    hdoj1002——大整数相加

    ### hdoj1002——大整数相加 #### 题目背景与目的 本题目来源于杭州电子科技大学的在线评测系统(HDOJ),编号为1002的大整数相加问题。该题目主要考察的是编程者对于大整数处理的基本技巧以及对数组、循环等基础...

    HDOJ题目分类 HDOJ题目分类

    【标题】:“HDOJ题目分类 HDOJ题目分类” HDOJ,全称为Happy DingO Online Judge,是一个在线编程竞赛平台,它为参赛者提供了大量编程题目进行练习和比赛,旨在提升编程技能和算法理解。HDOJ的题目分类是帮助用户...

    HDOJ 80题 Java

    【标题】"HDOJ 80题 Java"是一份专为Java程序员设计的在线编程挑战集合,源自杭州电子科技大学(HDOJ)的在线评测系统。这些题目旨在帮助Java开发者提升算法理解与编程能力,同时也为那些习惯于C++但希望在Java环境...

    hdoj2066最短路

    根据给定的文件信息,我们可以总结出以下关于“hdoj2066最短路径”的相关知识点: ## hdoj2066最短路径概述 ### 标题解析:“hdoj2066最短路” - **hdoj**:High Density Online Judge(高密度在线评测系统),是...

    hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000

    【标题】"hdoj.rar_Dividing HDOJ_OJ 1082_hdoj 10_杭电oj_杭电oj1000" 涉及的知识点主要围绕着“杭电在线判题系统(HDOJ)”以及其中的题目1082和10系列题目。HDOJ是杭州电子科技大学主办的一个在线编程竞赛平台,...

    HDOJ离线版

    《HDOJ离线版:探索编程竞赛的智慧宝库》 HDOJ,全称为“杭州电子科技大学在线评测系统”(Hangzhou Dianzi University Online Judge),是中国早期的编程竞赛平台之一,深受广大编程爱好者和在校学生的喜爱。HDOJ...

    hdoj--acm题目,有注释

    "hdoj--acm题目,有注释" 本资源提供了多个 ACM 题目的解决方案,代码都带有注释,非常适合初学者学习。下面是对每个题目的知识点总结: 2000:本题目要求输入三个字符,输出按照从小到大排序的结果。本代码使用了...

    HDOJ部分简单题(JAVA)

    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:杭电OJ题目源码记录 —— a source code of hdoj acm problem archive

    hdoj-problem-archive 杭电OJ题目源码记录 —— a source code of hdoj acm problem archive 简介 此项目为 的 题目以及代码仓库 src 中每一个文件夹代表一个题目 每个文件夹中都有 原题文档介绍.md 原题文档介绍.md...

    hdoj杭电入门训练题

    ### hdoj杭电入门训练题 #### 概述 杭电在线评测系统(HDOJ)是中国杭州电子科技大学提供的一套在线编程题库平台,主要用于计算机程序设计竞赛(ACM-ICPC)的训练与选拔。对于初学者而言,通过解决HDOJ中的题目可以...

    hdoj 2013 多校训练2标程+解题报告

    “hdoj 2013 多校训练2标程+解题报告”这个标题指的是2013年举行的一场由hdoj(HDU Online Judge,即杭州电子科技大学在线评测系统)组织的多校联合编程训练活动的第二阶段。其中,“标程”是指官方提供的正确解答...

    求回文子串_O(n)_manacher算法

    例如,在解决HDOJ_3068_最长回文子串问题时,Manacher算法能够快速准确地找出给定字符串中的最长回文子串,为各种文本分析、模式匹配等任务提供了高效的解决方案。 综上所述,Manacher算法作为一种专门针对回文子串...

    hdoj1001标程

    hdoj1001标程

    HDOJ1002

    ACM ICPC HDOJ1002

    hdoj 2013 多校训练4标程+解题报告

    【标题解析】:“hdoj 2013 多校训练4标程+解题报告”这个标题表明,这是一个关于2013年Happy Dream Online Judge(简称hdoj)组织的多校联合编程训练的资料。"4标程"意味着包含了四道题目(或者可能是四个阶段)的...

    HDOJ1001

    ACM ICPC HDOJ1001

    hdoj1004 解题代码 答案

    hdoj1004,解题代码,答案代码,欢迎下载

    OJ.tar.gz_HDOJ _OJ源码_oj

    【OJ.tar.gz_HDOJ _OJ源码_oj】是一个包含编程竞赛平台HDOJ(Happy Ding Octopus Judge)部分源代码的压缩文件。这个压缩包的主要目的是供学习和研究使用,尤其是针对50至60题目的解题算法和系统实现。通过分析这些...

    HDOJ.rar_HD_HDOJ

    【标题】"HDOJ.rar_HD_HDOJ" 是一个与HDU(杭州电子科技大学)在线判题系统HDOJ相关的压缩包文件,其中包含了大量编程题目的源代码。 【描述】提到,这个压缩包包含了几百道HDOJ题目的源代码,这意味着它是一个宝贵...

    HDOJ1003

    ACM ICPC HDOJ1003

Global site tag (gtag.js) - Google Analytics