POJ3261——重复K次的子串

2024-06-22 18:58
文章标签 重复 子串 poj3261

本文主要是介绍POJ3261——重复K次的子串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:给定长度为N的整数串,问至少重复K次的子串最长是多少,重复子串之间可以重迭。

求出SA与Height数组,首先将问题转为判定性问题,即:给定长度L,问存不存在长度为L且重复K次的子串。然后二分搜索最大的可能的L即可。

存在长度为L且重复K次的子串等价于:Height数组中存在一个长度至少为K-1的区间[i,j],Height[i,j]的值全部都不小于L。

另外源数组中的元素取值范围在百万之间,使用基数排序可能会出问题。但是数组长度最多只有2万, 说明数组中各异的值最多只有2万,因此做一个离散化再来套罗穗骞论文的代码模板。当然也可以改造一下,使用快排。

//32ms
#include <cstdio>
#include <algorithm>
using namespace std;int const SIZE = 20005;
//分隔符,多串连接时需要用到,第0个为结束符,肯定用到
char const DELIMETER[] = {'#'};
int const DELIMETER_CNT = 1;
//字母表的字母个数
int const ALPHA_SIZE = DELIMETER_CNT + 26;
//char转int
inline int tr(char ch){if ( DELIMETER[0] == ch ) return 0;return ch - 'a' + 1;
}
//辅助宏,以下划线开头
#define _F(x) ((x)/3+((x)%3==1?0:tb))
#define _G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
//辅助数组,以下划线开头
int _wa[SIZE],_wb[SIZE],_wv[SIZE],_ws[SIZE];
//辅助函数
int _c0(int const r[],int a,int b){return r[a] == r[b]&& r[a+1] == r[b+1]&& r[a+2] == r[b+2];
}
int _c12(int k,int *r,int a,int b){if( 2 == k ) return r[a]<r[b] || ( r[a]==r[b]&&_c12(1,r,a+1,b+1) );return r[a]<r[b] || ( r[a]==r[b]&&_wv[a+1]<_wv[b+1] );
}
void _sort(int const r[],int *a,int *b,int n,int m){int i;for(i=0;i<n;i++) _wv[i] = r[a[i]];for(i=0;i<m;i++) _ws[i] = 0;for(i=0;i<n;i++) _ws[_wv[i]]++;for(i=1;i<m;i++) _ws[i] += _ws[i-1];for(i=n-1;i>=0;i--) b[--_ws[_wv[i]]] = a[i];return;
}
//后缀数组的dc3算法,使用此dc3算法一定要保证r与sa的最大长度不小于3倍原长度
//r: 源数组,且除r[n-1]外,其余r[i]>0
//n: r的长度
//m: r中的元素取值的上界,即任意r[i]<m
//sa:后缀数组,即结果
void dc3(int r[],int n,int m,int sa[]){int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;r[n] = r[n+1] = 0;for(i=0;i<n;i++) if(i%3!=0) _wa[tbc++]=i;_sort(r+2,_wa,_wb,tbc,m);_sort(r+1,_wb,_wa,tbc,m);_sort(r,_wa,_wb,tbc,m);for(p=1,rn[_F(_wb[0])]=0,i=1;i<tbc;i++)rn[_F(_wb[i])] = _c0(r,_wb[i-1],_wb[i])?p-1:p++;if(p<tbc) dc3(rn,tbc,p,san);else for(i=0;i<tbc;i++) san[rn[i]]=i;for(i=0;i<tbc;i++) if(san[i]<tb) _wb[ta++] = san[i]*3;if(n%3==1) _wb[ta++]=n-1;_sort(r,_wb,_wa,ta,m);for(i=0;i<tbc;i++) _wv[_wb[i] = _G(san[i])] = i;for(i=0,j=0,p=0;i<ta&&j<tbc;p++)sa[p] = _c12(_wb[j]%3,r,_wa[i],_wb[j]) ? _wa[i++] : _wb[j++];for(;i<ta;p++) sa[p] = _wa[i++];for(;j<tbc;p++) sa[p] = _wb[j++];return;
}
//计算rank数组与height数组
//r:  源数组
//sa: 后缀数组
//n:  源数组的长度
//rank: rank数组,即计算结果
//height: height数组,即计算结果
void calHeight(int const r[],int const sa[],int n,int rank[],int height[]){int i,j,k=0;for(i=1;i<n;i++) rank[sa[i]]=i;for(i=0;i<n-1;height[rank[i++]]=k)for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);return;
}void dispArray(int const a[],int n){for(int i=0;i<n;++i)printf("%d ",a[i]);printf("\n");
}int R[SIZE*3],SA[SIZE*3];//3倍!!!
int Rank[SIZE],Height[SIZE];
int N,K;
int A[SIZE];
int Idx[1000005];
bool read(){if ( EOF == scanf("%d%d",&N,&K) ) return false;//输入的可能取值为1000000,做一个离散化可以到20000for(int i=0;i<N;++i)scanf("%d",A+i),R[i]=A[i];sort(A,A+N);int n = unique(A,A+N) - A;for(int i=0;i<n;++i)Idx[A[i]] = i + 1;for(int i=0;i<N;++i) R[i] = Idx[R[i]];R[N++] = 0;return true;
}
//判断n值是否满足条件
//Height数组中至少连续K-1个值不小于v
bool check(int v){int i = 1;while( i < N ){while( i < N && Height[i] < v ) ++i;int k = 0;while( i + k < N && Height[i+k] >= v && k < K - 1 ) ++k;if( K - 1 == k ) return true;i += k + 1;}return false;
}
int proc(){dc3(R,N,N+2,SA);calHeight(R,SA,N,Rank,Height);/*dispArray(R,N);dispArray(SA,N);dispArray(Rank,N);dispArray(Height,N);//*///二分法查找至少重复了k次的子串的最长长度,可重迭int left = 0;//答案至少是0int right = N - K;//答案至多是N-kdo{int mid = ( left + right ) >> 1;if ( check(mid) ) left = mid + 1;else right = mid - 1;}while( left <= right );return right;
}int main(){while( read() )printf("%d\n",proc());return 0;
}

这篇关于POJ3261——重复K次的子串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1085139

相关文章

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

C# 防止按钮botton重复“点击”的方法

在使用C#的按钮控件的时候,经常我们想如果出现了多次点击的时候只让其在执行的时候只响应一次。这个时候很多人可能会想到使用Enable=false, 但是实际情况是还是会被多次触发,因为C#采用的是消息队列机制,这个时候我们只需要在Enable = true 之前加一句 Application.DoEvents();就能达到防止重复点击的问题。 private void btnGenerateSh

PHP最长单一子串

<?php//方法一$s='abcccddddddcdefg';$max='';while($s!=''){$i=0; while($i<strlen($s) && $s[$i]==$s[0]) $i++;if ($i>strlen($max)){$max=substr($s,0,$i);} $s=substr($s,$i);}echo $m

MySQL脏读、不可重复读、幻读(虚读)

事务的特性: 原子性:指处于同一个事务中的多条语句是不可分割的。一致性:事务必须使数据库从一个一致性状态变换到另外一个一致性状态。比如转账,转账前两个账户余额之和为2k,转账之后也应该是2K。隔离性:指多线程环境下,一个线程中的事务不能被其他线程中的事务打扰持久性:事务一旦提交,就应该被永久保存起来。 事务隔离性问题: 如果不考虑事务的隔离性,会出现以下问题: 脏读:指一个线程中的事务读取到

【第0006页 · 数组】寻找重复数

【前言】本文以及之后的一些题解都会陆续整理到目录中,若想了解全部题解整理,请看这里: 第0006页 · 寻找重复数         今天想讨论的一道题在 LeetCode 上评论也是颇为“不错”。有一说一,是道好题,不过我们还是得先理解了它才算真正的好题。这里我们展示一种使用二进制的做法,希望能帮到你哟! 【寻找重复数】给定一个包含 n + 1 个整数的数组 nums ,其数字都

R语言统计分析——重复测量方差分析

参考资料:R语言实战【第2版】         所谓重复测量方差分析,即受试者被测量不止一次。本例使用数据集市co2数据集:因变量是二氧化碳吸收量(uptake),自变量是植物类型(Type)和七种水平的二氧化碳浓度(conc)。Type是组间因子,conc是组内因子。Type已经被存储为一个因子变量,还需要将conc转换为因子变量。分析过程如下: # 将conc变量转化为因子变量CO2$c