因果循环，报应不爽。世间的一切都在这因果的操控下，缓缓运作。本来，这一切都不为人所知，直到默默无名的科学家凤凰院凶魔，偶然进入了世界的里端。
在那里，他看到的是在空中飞舞的具现化成锁链的因果律。
作为科学狂人，他马上开始研究因果律锁链，全然不顾他现在所处的异常空间。
凶魔发现因果律锁链是由4种不同的锁环环环相扣而成的。他将它们编号为a~d。凶魔认为这4个环的不同排列方式中，蕴含着因果律本质。为了进一步研究因果律锁链，他采取了由局部到个体的研究方法。他选了一条他认为比较有规律的因果律锁链，然后他将这条因果律的锁环，用编号一一记下来。
他想要寻找到这条因果链的本质。他认为将这条因果链断成k段之后，这k段破碎的因果链的最长连续公共子串是关键。他想要找到所有不同的断裂方案中，最长连续公共子串最长的最优方案。这些最优方案中，字典序最小的最长连续公共子串就是他想要的结果。
由于他花费了大量的精力用编号记下了这条因果律锁链，他已经筋疲力尽了。你能帮他完成接下来的工作吗？
输入格式：
第一行2个正整数，第一个整数n表示他记下的因果律锁链编号。第二个整数k表示他将锁链断成的段数。
第二行n个小写字母，表示他记下的因果律锁链。
（n≤Nmax， k≤n）
输出格式：
输出只有一行，就是最优方案中，字典序最小的最长连续公共子串。如果不存在，输出“Kyoma is wrong.”（不包括双引号）。
样例输入：
样例输入一
5 2
ababa
样例输入二
5 5
abaaa
样例输入三
6 2
abaaaa
样例输出：
样例输出一
ab
样例输出二
Kyoma is wrong.
样例输出三
aa
数据范围：
数据编号 Nmax
1 50
2 50
3 500
4 500
5 100000
6 100000
7 100000
8 100000
9 100000
10 100000
时间限制：
1S
空间限制：
256M
看来对于10W以上的数据，map的确很慢。。。
先用后缀数组或者hash弄一下。。
二分一下最长的答案。然后(map搞会T。。)排序贪心一下。。
原题解：
一个显然的结论：
必有一个最优解，每个子串的前缀就是答案串。
水法1：枚举答案起始位置，枚举答案结束位置，暴力查询出现了多少次（不可重叠）。若出现次数超过k，则更新最优解。
时间：Θ（n^4）
期望得分：20分。
水法2：枚举答案起始位置，枚举答案结束位置，用字符串hash查询出现了多少次（不可重叠）。若出现次数超过k，则更新最优解。
时间：Θ（n^3）
期望得分：40分。
水法还有很多很多……
正解1：后缀树组+二分答案
构建后缀数组。显然答案串的长度跟它在串中出现的个数呈负相关。
二分答案串的长度L。
按字典序将后缀分成多个公共前缀大于L的集合。每个集合内利用贪心（即不断取最靠左的不重叠的串）可以求出不重叠的答案串个数。若大于k则增长L，否则缩短L。
时间：Θ（nlogn）
期望得分：100分。
正解2：字符串hash+二分答案
hash有很多很多种。在这里我会的最实用的，就是某我不知道叫什么名字的hash。此hash主要思想与进制转换有相似之处，详情请看后文……
hash预处理。
二分答案L。
从左到右扫描原串，计算出每个位置长度为L的字符串的hash值，记录每个hash值出现的位置。
对于相同的hash值的集合，利用贪心（即不断取最靠左的不重叠的串），即可求出每个hash值对应的串出现的次数。
时间：Θ（nlogn）
期望得分：100分。
gy补充：
实际处理的时候还有一些细节，该哈希的本质是拼人品。如果两个串的哈希值相等，我们认为它们相等。
从而可以用一个64位整数来压缩串使得我们可以O(1)判断两串是否显得。
判断时，将此整数mod一个数放在数组里，用类似哈希的拉链法判重。
正解应该还有不少。
关于哈希……这里提供一个例子，有兴趣的读者可以将以下代码放大后查看。（我放到最大了还是看不到啊！！）
细心的读者不难发现，以上的内容有点粗糙。这是锻炼为了读者的独立思考能力。
自己写的hash（本来写的双模的。。结果我以为那个太慢。。改了个摸2^64...结果还是T。。结果就排序了。。）:
#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
#define rep(i,l,r) for (int i=l;i<=r;++i)
typedef long long LL;
typedef std::pair<LL,LL> PLL;
const int MAX_N=100050;
char c[MAX_N];
int n,k;
const LL base=127;
LL pow[MAX_N];
LL hash[MAX_N];
LL f(int l,int r){
return hash[r]-hash[l-1]*pow[r-l+1];
}
void gethash(){
pow[0]=1;
rep(i,1,n){
pow[i]=pow[i-1]*base;
hash[i]=hash[i-1]*base+c[i];
}
}
PLL h[MAX_N];
bool check(int l){
rep(i,1,n-l+1) h[i]=PLL(f(i,i+l-1),i);
int num=n-l+1;
std::sort(h+1,h+num+1);
int last=1;
rep(i,1,num){
if (h[i].first!=h[i+1].first){
if (i-last+1>=k){
int cnt=0,pos=0;
rep(j,last,i){
if (pos<h[j].second){
cnt++;
pos=h[j].second+l-1;
}
}
if (cnt>=k) return true;
}
last=i+1;
}
}
return false;
}
std::map<LL,PLL> map;
void printans(int l){
map.clear();
int p=0;PLL tp;LL hash;
rep(i,1,n-l+1){
hash=f(i,i+l-1);
tp=map[hash];
if (i<=tp.first) continue;
tp.first=i+l-1;
if (++tp.second>=k){
if (!p) p=i; else
rep(j,0,l-1) if (c[i+j]!=c[p+j]){
if (c[i+j]<c[p+j]) p=i;
break;
}
}
map[hash]=tp;
}
rep(i,0,l-1) printf("%c",c[p+i]);
}
void calc(int l,int r){
if (!check(l)){printf("Kyoma is wrong.");return;}
while (r-l>1){
int mid=l+r>>1;
if (check(mid)) l=mid;
else r=mid;
}
printans(l);
}
int main(){
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
scanf("%d%d",&n,&k);
scanf("%s",c+1);
gethash();
calc(1,n/k+1);
}
在送一份XYZ的suffix array（感觉很漂亮~~）：
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 110000
int n, k, q, h, mid, ss[N], sa[N], wa[N], wb[N], wv[N], rank[N], height[N], tx[N];
char S[N];
bool cmp(int *y, int j, int a, int b) {
return y[a] == y[b] && y[a + j] == y[b + j];
}
void da(char *S, int n, int m) {
int *x = wa, *y = wb, i, j, p;
for (i = 0; i < n; i++) ss[x[i] = S[i]]++;
for (i = 1; i < m; i++) ss[i] += ss[i - 1];
for (i = 0; i < n; i++) sa[--ss[x[i]]] = i;
for (j = 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++) ss[i] = 0;
for (i = 0; i < n; i++) ss[wv[i]]++;
for (i = 1; i < m; i++) ss[i] += ss[i - 1];
for (i = n - 1; i >= 0; i--) sa[--ss[wv[i]]] = y[i];
for (swap(x, y), x[sa[0]] = 0, p = i = 1; i < n; i++)
x[sa[i]] = cmp(y, j, sa[i], sa[i - 1]) ? p - 1 : p++;
}
}
void calcHeight(char *S, int n) {
int i, j, k = 0;
for (i = 0; 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]; S[i + k] == S[j + k]; k++);
}
bool can(int x) {
int q, h, i;
for (q = 1; q <= n; q = h + 1) {
for (h = q; h < n && height[h + 1] >= x; h++);
for (i = q; i <= h; i++) tx[i] = sa[i];
sort(tx + q, tx + h + 1);
int sum = 0, prep = 0;
for (i = q; i <= h; i++) if (tx[i] >= prep && tx[i] + x <= n) sum++, prep = tx[i] + x;
if (sum >= k) return true;
}
return false;
}
void out(int x) {
int q, h, i;
for (q = 1; q <= n; q = h + 1) {
for (h = q; h < n && height[h + 1] >= x; h++);
for (i = q; i <= h; i++) tx[i] = sa[i];
sort(tx + q, tx + h + 1);
int sum = 0, prep = 0;
for (i = q; i <= h; i++) if (tx[i] >= prep && tx[i] + x <= n) sum++, prep = tx[i] + x;
if (sum >= k) {
for (i = sa[q]; i < sa[q] + x; i++) printf("%c", S[i]);
printf("\n");
return ;
}
}
}
int main() {
scanf("%d%d%s", &n, &k, S);
da(S, n + 1, 300);
calcHeight(S, n);
q = 0; h = n + 1;
while (q < h - 1) {
mid = (q + h) / 2;
if (can(mid)) q = mid;
else h = mid;
}
if (!q) printf("Kyoma is wrong.\n");
else out(q);
}
当然再来一份fancy coder(压得很短??):
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<string>
#include<bitset>
#include<iomanip>
#include<iostream>
#include<cmath>
using namespace std;
#define rep(i,x,y) for(i=x;i<=y;i++)
#define _rep(i,x,y) for(i=x;i>=y;i--)
#define CL(S,x) memset(S,x,sizeof(S))
#define CP(S1,S2) memcpy(S1,S2,sizeof(S2))
#define ALL(x,S) for(x=S.begin();x!=S.end();x++)
#define sqr(x) ((x)*(x))
#define mp make_pair
#define fi first
#define se second
#define upmin(x,y) x=min(x,y)
#define upmax(x,y) x=max(x,y)
#define pb push_back
#define COUT(S,x) cout<<fixed<<setprecision(x)<<S<<endl
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
template<class T> inline void read(T&x){bool fu=0;char c;for(c=getchar();c<=32;c=getchar());if(c=='-')fu=1,c=getchar();for(x=0;c>32;c=getchar())x=x*10+c-'0';if(fu)x=-x;};
inline char getc(){char c;for(c=getchar();c<=32;c=getchar());return c;}
const int N=200010;
int n,i,j,k,g,l,r,p,start;
char st[N];int a[N],z[N];
int sa[N],rank[N],sa2[N],rank2[N],h[N],sum[N];
void suffix()
{
int i,j,p;
rep(i,1,n)sum[a[i]]++;
rep(i,1,128)sum[i]+=sum[i-1];
_rep(i,n,1)sa[sum[a[i]]--]=i;
rank[sa[1]]=j=1;rep(i,2,n){if(a[sa[i]]!=a[sa[i-1]])++j;rank[sa[i]]=j;}
for(p=1;j<n;p*=2)
{
CL(sum,0);CP(rank2,rank);
j=0;rep(i,n-p+1,n)sa2[++j]=i;
rep(i,1,n)if(sa[i]>p)sa2[++j]=sa[i]-p;
rep(i,1,n)sum[rank[sa2[i]]]++;
rep(i,1,n)sum[i]+=sum[i-1];
_rep(i,n,1)sa[sum[rank[sa2[i]]]--]=sa2[i];
rank[sa[1]]=j=1;rep(i,2,n){if(rank2[sa[i]]!=rank2[sa[i-1]]||rank2[sa[i]+p]!=rank2[sa[i-1]+p])++j;rank[sa[i]]=j;}
}
p=0;
rep(i,1,n)if(rank[i]>1)
{
j=sa[rank[i]-1];
while(a[i+p]==a[j+p])p++;
h[rank[i]]=p;
if(p)p--;
}
}
bool ok(int K)
{
if(K==0)return 1;
int i,j,p,res,tot;
for(i=1;i<=n;i=j+1)
{
for(;i<=n&&h[i]<K;i++);if(i>n)break;
for(j=i;j<=n&&h[j]>=K;j++);j--;
z[0]=0;rep(p,i-1,j)z[++z[0]]=sa[p];
sort(z+1,z+1+z[0]);
res=z[1];tot=1;rep(p,2,z[0])if(z[p]-res>=K)res=z[p],tot++;
if(tot>=g){start=res;return 1;}
}
return 0;
}
int main()
{
//freopen("2.in","r",stdin);freopen("2.out","w",stdout);
read(n);read(g);
scanf("%s",st+1);
if(g==1){rep(i,1,n)printf("%c",st[i]);printf("\n");return 0;}
rep(i,1,n)a[i]=st[i]-'a'+1;
suffix();
for(l=0,r=n;l<r;)
{
int mid=(l+r+1)/2;
if(ok(mid))l=mid;else r=mid-1;
}
if(l==0)printf("Kyoma is wrong.\n");
else{rep(i,start,start+l-1)putchar(st[i]);printf("\n");}
scanf("\n");
return 0;
}
![GridView终极用法(一)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)