BZOJ3796: Mushroom追妹纸 后缀数组+二分+暴力 - Shinbokuow - 不试着去思考的话,不就已经死去了吗 热门ag视讯平台|官方,ag手机客户端登录|官网,ag国际厅ag
BZOJ3238: [Ahoi2013]差异 后缀数组+单调队列
BZOJ3065:带插入区间K小值 ScapegoatTree套动态开点线段树

BZOJ3796: Mushroom追妹纸 后缀数组+二分+暴力

shinbokuow posted @ Dec 16, 2014 11:45:49 PM in BZOJ with tags 二分 后缀数组 , 3212 阅读

本题其实就是有限制的最长公共子串(注意\(s3\)那个限制千万别看反!!!)

于是乎本人无脑暴力,先求出后缀数组,二分的时候先在height连续块中暴力求一遍KMP,看一下这个串合不合适。

不会算严格的时间复杂度,不过貌似也不是特别慢。

(注:下面的DC3是有bug的,请不要无脑搬运)

#include
#include
#include
#include
using namespace std;
 
#define N 110010
int v[N*3],sa[N*3],qa[N],qb[N],val[N];
inline void RadixSort(int*v,int*q,int*sa,int n,int m){
    register int i,j;static int c[N];
    for(i=0;i=0;--i)sa[--c[v[q[i]]]]=q[i];
}
inline bool cmp1(int*v,int a,int b){
    return v[a]==v[b]&&v[a+1]==v[b+1]&&v[a+2]==v[b+2];
}
inline bool cmp2(int d,int*v,int a,int b){
    if(d==1)return v[a]<><><><>>1;
        bool ac=0;
        for(i=1;i=mid){
                 
                int ins=sa[i];bool cannot=0;
                for(k=0,j=ins;j=mid;++j);
                /*for(k=i-1;k<=j;++k){
                    if(sa[k]>=0&&sa[k]<=l1-1&&sa[k]+mid-1=l1+1&&sa[k]<=l1+l2&&sa[k]-l1-1+mid-1
ww140142 说:
ag111|HOME

大爷,在一个字符串里找另一个字符串出现的所有位置怎么做。。

Avatar_small
wyfcyx 说:
ag111|HOME

@ww140142: 才反应过来,不要叫我大爷。。。我哪够资格被称为“大爷”啊?

vivo mobile price in 说:
ag111|HOME

its china language I know it

xiaomi mobile price 说:
ag111|HOME

maybe post is language category

tecno mobile price i 说:
ag111|HOME

Thank you for share good info


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter