本文主要是介绍poj3261（可重复k次的最长子串），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：可重复k次的最长子串解题思路：求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N，但实际复杂度很低。题目数据也比较水，不然估计过不了。
代码入下：
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<string>
#include<vector>
#define N 1000005
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 10e-6using namespace std;
int wa[N],wb[N],wv[N],WS[N],r[N],sa[N];
bool cmp(int *r,int a,int b,int l)
{return r[a] == r[b] && r[a+l] == r[b+l];
}
int rank[N],height[N];
void calheight(int n)
{int i,j,k = 0;for(i = 1; i <= n; i++) rank[ sa[i] ] = i;for(i = 0; i < n; height[ rank[i++] ] = k)for(k ? k-- : 0, j = sa[ rank[i]-1 ]; r[i+k] == r[j+k]; k++);
}
void da(int n,int m)
{int i, j, p, *x = wa, *y = wb, *t;for(i = 0; i < m; i++) WS[i] = 0;for(i = 0; i < n; i++) WS[ x[i] = r[i] ]++;for(i = 1; i < m; i++) WS[i] += WS[i-1];for(i = n-1; i >= 0; i--) sa[ --WS[ x[i] ] ] = i;for(j = 1, p = 1; p < n; j *= 2,m = p){for(p = 0, i = n-j; i < n; i++) y[p++] = i;for(i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i] - j;for(i = 0; i < n; i++) wv[i] = x[ y[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--) sa[ --WS[ wv[i] ] ] = y[i];for(t = x,x = y,y = t,p = 1,x[ sa[0] ] = 0,i = 1; i < n; i++)x[ sa[i] ] = cmp(y,sa[i-1],sa[i],j) ? p-1 : p++;}
}int main()
{int n,k;while(scanf("%d%d",&n,&k) != EOF){int i;for(i = 0; i < n; i++){scanf("%d",&r[i]);r[i]++;}r[n] = 0;da(n+1,1000001);calheight(n);// for(i = 0; i < n; i++)// cout<<sa[i]<<" ";// cout<<endl;k--;int _min = inf,ans = 0;for(i = 2; i - 2 < k; i++)_min = min(_min,height[i]);if(_min > ans) ans = _min;for(int j = 2; i <= n; i++, j++){if(_min == height[j]){_min = inf;for(int o = j+1; o <= i; o++)_min = min(_min,height[o]);}if(height[i] < _min) _min = height[i];if(_min > ans) ans = _min;}printf("%d\n",ans);}return 0;
}
/*
6 2
2 1 5 1 5 1
*/
这篇关于poj3261（可重复k次的最长子串）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
