天矢の翼

去年合肥赛区网络赛一道算是最难的题。印象中比赛中没有人做出来。而后现场赛的练习赛居然又把这题给搞上来了。虽然大家都是直接贴样例过的。。。（摊手）以此引发了广大同人战斗之热血....

于是继04年徐智磊对SA介绍之后，在WC2009论文集里出现了一篇对后缀数组题目所做的总结。

此题先定义了这样的名词：
重复子串：如果一个子串是由一个以上的子串连续重复出现所构成的，那么这个子串叫原串的一个重复子串，那么在这个子串中次级子串连续重复出现的次数，...

没想到俺在POJ的第400题是男人八题之一

继续是后缀数组+二分扫描这一老路

二分答案，然后判断被分区间的两边sa数组最值。

这里由于旋律是比我们所求的差的相同部分多一个的。所以判断时候不是down+X<=up而是down+X<up.

#include<iostream>
#include<algorithm>
using namespace...

跟POJ1226类似。只不过这个求严格大于一半的个数并且要记录。

不过我这代码。。太没效率了。。等会了线性排序再说。。

#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<memory>
#include<vector&g...

很久没这么激动了呵呵~気持ち~

题目给定n个串，求一个最大子串长度，使得它或者它的逆向串在每个串中出现。

于是求出后缀数组之后。

枚举答案长度k。于是height数组就被分成了几个height[i]>=k的连续区间，剩下的就是判断一下是不是有区间包含所有的串就可以了~~

#include<iostream>
#include<string>
#in...

N年以前就学了这东西一直用不好。。。orz

这个是代码。。nlgnlgn的。。。桶排还是不大会使。。

BS我吧。。。


#include<iostream>
#include<string>
#define MAXN 50010
using namespace std;
char s[MAXN];
int height[MAXN],sa[M...