【poj 3261】Milk Patterns 二分+后缀数组_WeZiH的博客-程序员宅基地

题意：给一个N项的序列（1<=N <= 20,000，每一项是不超过1,000,000的自然数），求至少出现K次的子串的最大长度，出现位置允许重叠。
嗯，满早他们就说这个题目是后缀数组，然后我当时还不会，学了几天嗯，学会了吧。。唉，后缀数组这个东西真的是细节多如麻~。然后当时学妹就用hash过了。嗯，
chrt的hash
有兴趣的可以看一下，虽然跑得比后缀数组慢但是代码短易于实现。
这个题目就是二分可能的长度，然后每次验证就可以了。嗯，于是验证的时候就用后缀数组暴力验证吧，头痛欲裂。不想分析时间复杂度这些东西了。直接贴代码吧，等有机会再详细解释吧。
代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

const int MAXN = 100005;

using namespace std;

int s[MAXN];
int sa[MAXN],r[MAXN],t[MAXN],t2[MAXN],c[MAXN],h[MAXN],n,k;

inline void build_sa(int m)
{
    int *x = t,*y = t2;

    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 = 0;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 p = 0;
        for(int i = n - k;i < n;i++) y[p++] = i;
        for(int i = 0;i < n;i++) if(sa[i] >= k) y[p++] = 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 = 0;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);
        p = 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] ? p - 1 : p++;
        if(p >= n) break;
        m = p;  
    } 

}

inline void build_Height()
{
    int i,j,k = 0;
    for(i = 0;i < n;i++) r[sa[i]] = i;
    for(i = 0;i < n;i++)
    {
        if(k) k--;
        j = sa[r[i] - 1];
        while(s[i+k] == s[j + k]) ++k;
        h[r[i]] = k;
    }
}

inline bool check(int M){
    int cnt = 1;
    for(int i = 1;i < n;i++){
        if(h[i] >= M){
            if(++cnt >= k) return true;
        }   else {
            cnt = 1;
        }
    }
    return cnt >= k;
}

int main()
{
    scanf("%d %d",&n,&k);

    for(int i = 0;i < n;i++)
        scanf("%d",&s[i]),
         ++s[i];

    n++;

    build_sa(256);

    build_Height();

    int L = 1,R = n,ans;

    while(L <= R){
        int M = (L+R) >> 1;
        if(check(M)) L = M + 1,ans = M;
        else R = M - 1;
    }

    cout<<ans;


    return 0;
}

本文链接：https://blog.csdn.net/Qantun_Mechanics/article/details/52960034

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

[30天轻松掌握JavaWeb视频]-xml案例(考生成绩管理系统)_Gins的博客-程序员宅基地

exam.xml 张三沈阳 89 李四大连 97 Student类package domainpublic class Student { private String idcard; private String examid; private String name; private String location; pr

全局变量和局部变量_如梦初醒！的博客-程序员宅基地

1.命名空间说明：命名空间(Namespace)是从名称到对象的映射，大部分的命名空间都是通过 Python 字典来实现的。命名空间提供了在项目中避免名字冲突的一种方法。各个命名空间是独立的，没有任何关系的，所以一个命名空间中不能有重名，但不同的命名空间是可以重名而没有任何影响。一般有三种命名空间：内置名称（built-in names）， Python 语言内置的名称，比如函数名 abs、char 和异常名称 BaseException、Exception 等等。全局名称（gl...

pl/sql编程语言_pl语言_HHRunning的博客-程序员宅基地

–pl/sql编程语言–pl/sql编程语言是对sql语言的扩展，是的sql语言具有过程化编程的特性–pl/sql编程语言比一般的过程化编程语言，更加灵活高效–pl/sql编程语言主要用来编写存储过程和存储函数等。--声明方法,定义变量--赋值操作可以用 := 也可以使用 into 查询语句赋值declare i number(2):=10; --数值型变量 ..._pl语言

C++入门篇(2)之引用,内联函数,auto和范围遍历_捕获一只小肚皮的博客-程序员宅基地

文章目录前言extern "C"引用1.概念2.语法3.引用特性4.常量引用5.引用做函数返回值6.引用注意点7.传值、传引用效率比较内联函数1.概念2.特性auto关键字1.概念2.auto的使用细则3.auto不能推导的场景基于范围的for循环(C++11)使用条件指针空值nullptr前言承接上文入门篇1,博主这次将会继续更新以下内容:extern ,引用 ,内联, auto ,范围for循环和 C++中的空指针表示法(温馨提示:都是讲解浅显的知识,后面会深入讲解.),浏览此文,大家可以根据上

python3.7用法_在Python3.7中使用请求库进行异步请求_weixin_39976382的博客-程序员宅基地

与lib一起请求的Lukasa说：At the current time there are no plans to support async and await. This is not because they aren't a good idea: they are. It's because to use them requires quite substantial code chan..._python 3.7.14 异步main

第三周作业_陈志彬的博客-程序员宅基地

实验作业1.输入课本各个例题，调试运行程序，并分析程序，将每一个程序改写2到3个版本，自己分析程序结果，然后再调试运行，核对分析结果的对错。2.编写程序输入一个三角形的三条边，计算其面积和周长；3.编写程序计算并输出课本本章习题3表达式的值并分析结果。4.编写一个程序，输入一个一元二次方程的三个系数，并计算其方程的解，然后输出。5.编写程序，自己确定一个加密