后缀数组一·重复旋律
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。
小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。旋律是一段连续的数列，相似的旋律在原数列可重叠。比如在1 2 3 2 3 2 1 中 2 3 2 出现了两次。
小Hi想知道一段旋律中出现次数至少为K次的旋律最长是多少？
输入
第一行两个整数 N和K。1≤N≤20000 1≤K≤N
接下来有 N 个整数，表示每个音的数字。1≤数字≤100
输出
一行一个整数，表示答案。
- 样例输入
8 2
1
2
3
2
3
2
3
1- 样例输出
4
后缀数组得到相邻公共前缀长度。
单调队列得到区间最小值。
多写几遍感觉后缀数组也没那么难了。
之前分享了一点后缀数组的资料，http://www.cnblogs.com/hua-dong/p/7751828.html。而且感觉后缀数组处理字符串最为强大，所以我在字符串处理工具中给它单独分组。马拉车，KMP都还比较好写，ac自动机和后缀数组真的就，要多写才行。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
int Rank[maxn],cntA[maxn],cntB[maxn],A[maxn],B[maxn];
int ch[maxn],sa[maxn],tsa[maxn],ht[maxn];
int q[maxn],pos[maxn],head,tail,ans,N,K;
void solve()
{
for (int i = ; i<N; i ++) cntA[i] = ;
for (int i = ; i<=N; i ++) cntA[ch[i]] ++;
for (int i = ; i<N; i ++) cntA[i] += cntA[i - ];
for (int i = N; i; i --) sa[cntA[ch[i]] --] = i;
Rank[sa[]] = ;
for (int i = ; i <= N; i ++)
{
Rank[sa[i]] = Rank[sa[i - ]];
if (ch[sa[i]] != ch[sa[i - ]]) Rank[sa[i]] ++;
}
for (int l = ; Rank[sa[N]] < N; l <<= )
{
for (int i = ; i <= N; i ++) cntA[i] = ;
for (int i = ; i <= N; i ++) cntB[i] = ;
for (int i = ; i <= N; i ++)
{
cntA[A[i] = Rank[i]] ++;
cntB[B[i] = (i + l <= N) ? Rank[i + l] : ] ++;
}
for (int i = ; i <= N; i ++) cntB[i] += cntB[i - ];
for (int i = N; i; i --) tsa[cntB[B[i]] --] = i;
for (int i = ; i <= N; i ++) cntA[i] += cntA[i - ];
for (int i = N; i; i --) sa[cntA[A[tsa[i]]] --] = tsa[i];
Rank[sa[]] = ;
for (int i = ; i <= N; i ++)
{
Rank[sa[i]] = Rank[sa[i - ]];
if (A[sa[i]] != A[sa[i - ]] || B[sa[i]] != B[sa[i - ]]) Rank[sa[i]] ++;
}
}
for (int i = , j = ; i <= N; i ++)
{
if (j) j --;
while (ch[i + j] == ch[sa[Rank[i] - ] + j]) j ++;
ht[Rank[i]] = j;
}
}
void getMax()//单调队列
{
int i,j;
for(i=;i<=N;i++)
{
while(head<=tail-&&ht[i]<q[tail]) tail--;
q[++tail]=ht[i];
pos[tail]=i;
if(i-pos[head]>=K) head++;
if(i-pos[head]<K&&q[head]>ans) ans=q[head];
}
}
int main()
{
int i,j;
scanf("%d%d",&N,&K);
K--;//height是两两比较，代表的是区间，所以要减一。
for(i=;i<=N;i++) scanf("%d",&ch[i]);
solve();
getMax();
printf("%d\n",ans);
return ;
}
（事实上，我觉得这个单调队列写得有问题，甚至在自己都知道写的时候这么想的，AC之后就没管了，现在想起来，是不是有些问题，但是还是不明白怎么AC的，难度是对的？）