题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=12580

【思路】

求出现次数不小于k次的最长可重叠子串和最后的出现位置。

法一:

后缀数组,二分长度,划分height。时间复杂度为O(nlogn)

法二:

Hash法。构造字符串的hash函数,二分长度,求出hash(i,L)后排序,判断是否存在超过k个相同hash 值得块即可。时间为O(nlog2n).

    法三:(UPD.16/4/6)

     SAM。求|right|。

注意划分height一定要精确且如果m=1需要特判

【代码1】

 //193ms
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std; const int maxn = +; int s[maxn];
int sa[maxn],c[maxn],t[maxn],t2[maxn];
void build_sa(int m,int n) {
int i,*x=t,*y=t2;
for(i=;i<m;i++) c[i]=;
for(i=;i<n;i++) c[x[i]=s[i]]++;
for(i=;i<m;i++) c[i]+=c[i-];
for(i=n-;i>=;i--) sa[--c[x[i]]]=i;
for(int k=;k<=n;k<<=) {
int p=;
for(i=n-k;i<n;i++) y[p++]=i;
for(i=;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=;i<m;i++) c[i]=;
for(i=;i<n;i++) c[x[y[i]]]++;
for(i=;i<m;i++) c[i]+=c[i-];
for(i=n-;i>=;i--) sa[--c[x[y[i]]]]=y[i];
swap(x,y);
p=; x[sa[]]=;
for(i=;i<n;i++)
x[sa[i]]=y[sa[i]]==y[sa[i-]] && y[sa[i]+k]==y[sa[i-]+k]?p-:p++;
if(p>=n) break;
m=p;
}
}
int rank[maxn],height[maxn];
void getHeight(int n) {
int i,j,k=;
for(i=;i<=n;i++) rank[sa[i]]=i;
for(i=;i<n;i++) {
if(k) k--;
j=sa[rank[i]-];
while(s[j+k]==s[i+k]) k++;
height[rank[i]]=k;
}
}
int limit,n,pos;
bool can(int L) { //一定要注意划分height数组的准确性
pos=-;
int cnt=,mx=sa[];
for(int i=;i<=n;i++) {
mx=max(mx,sa[i]);
if(height[i]<L) cnt=,mx=sa[i];
else {
if(++cnt>=limit) pos=max(pos,mx);
}
}
return pos>=;
} char expr[maxn];
int main() {
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
while(scanf("%d",&limit)== && limit) {
scanf("%s",expr);
n=strlen(expr);
for(int i=;i<n;i++) s[i]=expr[i]; s[n]=; build_sa('z'+,n+);
getHeight(n); if(limit==) { printf("%d 0\n",n); continue; }
int L=,R=n+;
while(L<R) {
int M=L+(R-L+)/;
if(can(M)) L=M; else R=M-;
}
if(!can(L)) printf("none\n");
else printf("%d %d\n",L,pos);
}
return ;
}

da

【代码2】

 //1628ms
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; typedef unsigned long long ULL;
const int maxn = +;
const int x = ; ULL hash[maxn],xp[maxn],H[maxn];
int m,n;
char s[maxn]; int cmp(const int& a,const int& b) {
return hash[a]<hash[b] || (hash[a]==hash[b] && a<b);
}
int pos,rank[maxn];
bool can(int L) {
pos=-;
for(int i=;i<n-L+;i++) hash[i]=H[i]-H[i+L]*xp[L],rank[i]=i;
sort(rank,rank+n-L+,cmp);
int cnt=;
for(int i=;i<n-L+;i++) {
if(!i || hash[rank[i]]!=hash[rank[i-]]) cnt=;
if(++cnt>=m) pos=max(pos,rank[i]);
}
return pos>=;
} int main() {
//freopen("in.in","r",stdin);
//freopen("outr.out","w",stdout);
while(scanf("%d",&m)== && m) {
scanf("%s",s);
n=strlen(s); H[n]=,xp[]=;
for(int i=n-;i>=;i--) H[i]=H[i+]*x+s[i]-'a';
for(int i=;i<=n;i++) xp[i]=xp[i-]*x; if(!can()) printf("none\n");
else {
int L=,R=n+;
while(L<R) {
int M=L+(R-L+)/;
if(can(M)) L=M; else R=M-;
}
can(L);
printf("%d %d\n",L,pos);
}
}
return ;
}

hash

最新文章

  1. NOIp2010 关押罪犯
  2. java,我准备好了
  3. c3p0配置
  4. Tomcat数据库连接池的配置方法总结
  5. Load an X509 PEM file into Windows CryptoApi
  6. Linux:一台apache服务器上部署多个项目的apache配置
  7. everything搜索工具小技巧
  8. 推荐一款自己的软件作品[豆约翰博客备份专家],新浪博客,QQ空间,CSDN,cnblogs博客备份,导出CHM,PDF(转载)
  9. Android 之 Spinner
  10. 转载:如何查看用户当前shell和修改用户登陆时的默认shell
  11. jquery,js常用特效名称
  12. 在SurfaceView中自由书写和擦除
  13. (转)shell:读取文件的每一行内容并输出
  14. DirectX SDK (June 2010)安装错误S1023的一个解决方法
  15. 洛谷 [P2486] 染色
  16. BZOJ 2694: Lcm [莫比乌斯反演 线性筛]
  17. VS2015编译GEOS的debug和release版本
  18. World Finals 2018 感想
  19. 第五周ip通信基础回顾
  20. Stackoverflow每日问题 系列前言

热门文章

  1. ASP.NET 系统对象 Request(一)
  2. HTML转义字符大全
  3. VM虚拟主机怎么设置网络
  4. centos安装zendopcache
  5. A/B测试
  6. Spring+C3P0数据库连接池配置
  7. MFC中的CDC,CClientDC,CPaintDC,CWindowDC的区别
  8. javac。java版本切换
  9. codevs 1088 神经网络
  10. jsp中的包含 include标签和ejb的小知识点
  11. web标准(复习)--4 纵向导航菜单及二级弹出菜单
  12. 找出数组中特定和数字下标(JAVA)
  13. php 解析url 和parse_url使用
  14. 使用UTF8-CPP转换unicode编码 附录:UTF8和UTF16和UTF32和Unicode编码
  15. Jquery对话框基本配置
  16. DOM相关知识
  17. Asp.NetMVC利用LigerUI搭建一个简单的后台管理详解(函登录验证)
  18. Springboot 使用过滤器进行加密解密(二)
  19. 16个富有创意的HTML5 Canvas动画特效集合
  20. mysql 通过慢查询日志查写得慢的sql语句