本文主要是介绍UVALive 4513 Stammering Aliens (hash+二分 or 后缀数组)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
大白书上的一道例题，后缀数组的模板题吧，今天想练练hash，结果就wa+Tle了一脸。
还真没见过不卡自然取模，而卡自行取模的题，今天算是见到了。。取了好几个x，还是发生了碰撞？！
题意：
让你根据所给字符串，找出至少出现m次的最长字符串，输出最长的长度和起始位置的最大值。
思路：
字符串hash+二分。（等学会了后缀数组再来套下模板）
二分len，然后判断长度是否合法。
判断过程：把长度为L的字符串hash值求出来，然后根据值大小从小到大排序（一开始我用map，TLE了几发），然后再统计就好了。
*书上的这个排序cmp函数值得研究一下。
code:
#include <bits/stdc++.h>
using namespace std;const int N = 40005;
const int x = 233;
typedef long long LL;
typedef unsigned long long ull;int m, len;
char ch[N];
ull X[N], h[N];
ull hv[N];
int rk[N];
int pos;inline ull getHash(int idx, int len) {return h[idx+len-1] - h[idx-1]*X[len];
}
bool cmp(const int &a, const int &b) {return hv[a] < hv[b] || ((hv[a] == hv[b]) && a < b);
}bool check(int mid) {int cnt = 0;pos = -1;for(int i = 1;i+mid-1 <= len; i++) {rk[cnt] = i-1;hv[cnt++] = getHash(i, mid);}sort(rk, rk+cnt, cmp);int c = 0;for(int i = 0;i < cnt; i++) {if(i == 0 || hv[rk[i]] != hv[rk[i-1]]) c = 0;if(++c >= m) pos = max(pos, rk[i]);}return pos >= 0;
}int main() {X[0] = 1;for(int i = 1;i < N; i++) X[i] = X[i-1]*x;while(scanf("%d", &m) && m) {scanf("%s", ch+1);len = strlen(ch+1);h[0] = 0;for(int i = 1;i <= len; i++) h[i] = h[i-1]*x+ch[i]-'a';int l = 1, r = len;int ans = -1;while(l <= r) {int mid = (l+r)>>1;if(check(mid)) {l = mid+1;ans = mid;}elser = mid-1;}if(ans == -1) puts("none");else {check(ans);printf("%d %d\n", ans, pos);}}return 0;
}
这篇关于UVALive 4513 Stammering Aliens (hash+二分 or 后缀数组)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
