poj3261 后缀数组求重复k次可重叠的子串的最长长度
Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 13669 | Accepted: 6041 | |
Case Time Limit: 2000MS |
Description
Farmer John has noticed that the quality of milk given by his cows varies from day to day. On further investigation, he discovered that although he can't predict the quality of milk from one day to the next, there are some regular patterns in the daily milk quality.
To perform a rigorous study, he has invented a complex classification scheme by which each milk sample is recorded as an integer between 0 and 1,000,000 inclusive, and has recorded data from a single cow over N (1 ≤ N ≤ 20,000) days. He wishes to find the longest pattern of samples which repeats identically at least K (2 ≤ K ≤ N) times. This may include overlapping patterns -- 1 2 3 2 3 2 3 1 repeats 2 3 2 3 twice, for example.
Help Farmer John by finding the longest repeating subsequence in the sequence of samples. It is guaranteed that at least one subsequence is repeated at least K times.
Input
Lines 2..N+1: N integers, one per line, the quality of the milk on day i appears on the ith line.
Output
Sample Input
8 2
1
2
3
2
3
2
3
1
Sample Output
/*
* Author: sweat123
* Created Time: 2016/6/28 16:24:57
* File Name: main.cpp
*/
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
#include<vector>
#include<cstdio>
#include<time.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1<<30
#define MOD 1000000007
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pi acos(-1.0)
using namespace std;
const int MAXN = ;
int wa[MAXN],wb[MAXN],wc[],n,height[MAXN],sa[MAXN],k,r[MAXN],Rank[MAXN];
void da(int *r,int *sa,int n,int m){
int *x = wa,*y = wb;
for(int i = ; i < m; i++)wc[i] = ;
for(int i = ; i < n; i++)wc[x[i] = r[i]] ++;
for(int i = ; i < m; i++)wc[i] += wc[i-];
for(int i = n - ; i >= ; i--)sa[--wc[x[i]]] = i;
for(int p = ,k = ; p < n; m = p,k <<= ){
p = ;
for(int i = n - k; i < n; i++)y[p++] = i;
for(int i = ; i < n; i++)if(sa[i] >= k)y[p++] = sa[i] - k;
for(int i = ; i < m; i++)wc[i] = ;
for(int i = ; i < n; i++)wc[x[y[i]]] ++;
for(int i = ; i < m; i++)wc[i] += wc[i-];
for(int i = n - ; i >= ; i--)sa[--wc[x[y[i]]]] = y[i];
swap(x,y);
p = ;
x[sa[]] = ;
for(int i = ; i < n; i++)
x[sa[i]] = (y[sa[i-]] == y[sa[i]] && y[sa[i-]+k] == y[sa[i]+k])?p-:p++;
}
}
void calheight(int *r,int *sa,int n){
for(int i = ; i <= n; i++)Rank[sa[i]] = i;
int k = ,j;
for(int i = ; i < n; height[Rank[i++]] = k){
for(k?k--:,j = sa[Rank[i]-]; r[j+k] == r[i+k]; k++);
}
}
int ok(int m,int n){
int num = ;
for(int i = ; i <= n; i++){
if(height[i] >= m){
num ++;
if(num + >= k)return ;
} else{
num = ;
}
}
return ;
}
void solve(){
int l,r,m,ans = ;
l = ,r = n;
while(l <= r){
m = (l + r) >> ;
if(ok(m,n)){
ans = max(m,ans);
l = m + ;
} else {
r = m - ;
}
}
printf("%d\n",ans);
}
int main(){
while(~scanf("%d%d",&n,&k)){
for(int i = ; i < n; i++){
scanf("%d",&r[i]);
}
r[n] = ;
da(r,sa,n+,);
calheight(r,sa,n);
solve();
}
return ;
}
最新文章
- Mardown字体颜色、背景色
- C#之数据分页
- iOS Aspect Fit,Aspect Fill,Scale To Fill
- BootStrap安装
- thinkphp 对数据库的操作
- poj2762 强连通+拓扑序
- idea+maven
- Convert Sorted List to Binary Search Tree java
- 关于WebGIS开源解决方案的探讨(转载)
- stm32之keil开发环境搭建
- 新概念英语(1-29)Come in, Amy.
- render函数data参数中的model选项
- redis在windows和Linux系统下的下载、安装、配置
- java结合node.js非对称加密,实现密文登录传参——让前后端分离的项目更安全
- Flink source task 源码分析
- Flask web开发之路十二
- proxy,https,git,tortoise git,ssh-agent,ssh-add,ssh,ssl,rsync
- AngularJS学习笔记(2)——与用户交互的动态清单列表
- NOIp 2018 货币系统 贪心
- phpstorm 设置