•题目地址HDU4080【Stammering Aliens】 •题目描述 • Ellie Arroway博士与一个外星文明建立了联系。然而，所有破解外星人讯息的努力都失败了，因为他们遇上了一群口吃的外星人。Ellie的团队发现，在每一条足够长的讯息中，最重要的单词都会以连续字符的顺序出现一定次数的重复，甚至出现在其他单词的中间；而且，有时讯息会以一种模糊的方式缩写；例如，如果外星人要说bab两次，他们可能会发送讯息babab，该讯息已被缩写，在第一个单词中第二个b被重用为第二个单词中的第一个b。 • 因此，一条讯息可能包含重复的相同单词一遍又一遍。现在，Ellie向您，S.R. Hadden，寻求帮助，以确定一条讯息的要点。 • 给出一个整数m和一个表示讯息的字符串s，请您查找至少出现m次的s的最长子字符串。例如，在讯息baaaababababbababbab中，长度为5个单词的babab包含3次，即在位置5、7和12处（其中下标索引从零开始），出现3次或更多次的子字符串不会比5更长（请参见样例输入中的第1个样例）；而且，在这条讯息中，有子串出现11次或更多次（请参见第2个样例）。如果存在多个 解决方案，则首选出现最右的子字符串（请参见第3个样例）。 • 输入 • 输入包含若干测试用例。每个测试用例在第一行给出一个整数m （m>=1），表示最小重复次数；下来的一行给出一个长度介于m和40000之间（包括m和40000）的字符串s。在s中，所有字符都是从“a”到“z”的小写字符。最后一个测试用例由m=0标识，程序不用处理。 • 输出 • 对每个测试用例输出一行。如果无解，则输出none；否则，在一行中输出两个用空格分隔的整数，第一个整数表示至少出现m次的子串的最大长度；第二个整数表示此子字符串的最右起始位置。 • 输入样例
3 baaaababababbababbab 11 baaaababababbababbab 3 cccccc 0• 输出样例
5 12 none 4 2思路： 寻找字符串中出现次数>=m次的子串 字符串hash。 二分子串的长度，然后处理出来所有这个长度的子串的值，排序后找有没有相同的大于等于m个即可。
代码：
#include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef unsigned long long ULL; const int N = 40010,base = 131; char str[N]; ULL p[N],h[N]; int len,pos,m; struct node{ ULL x; int px; }tmp[N]; bool cmp(node a,node b) { if(a.x == b.x) return a.px < b.px; return a.x < b.x; } ULL gethash(int l,int r) { return h[r] - h[l - 1] * p[r - l + 1]; } bool isok(int n) { pos = -1; int k = 0; for(int i = len - n + 1;i >= 1;i--) { tmp[k].x = gethash(i,i+n-1);//处理出所有长度为n的子串的值 tmp[k++].px = i; } sort(tmp,tmp+k,cmp); int cnt = 1; if(m == 1) pos = 1; for(int i = 1;i < k;i++) { if(tmp[i].x == tmp[i-1].x) { cnt++; if(cnt >= m) pos = max(pos,tmp[i].px); } else cnt = 1; } return pos != -1; } void makehash() { h[0] = 0;p[0] = 1; for(int i = 1;i <= len;i ++ ) { h[i] = h[i - 1] * base + str[i] - 'a' + 1; p[i] = p[i - 1] * base; } } int main() { while(scanf("%d",&m)&&m) { scanf("%s",str + 1); len = strlen(str + 1); makehash(); int l=1,r=len,ans=-1,ansp; pos=-1; while(l <= r) { int mid = (l+r)/2; if(isok(mid)) { ans = mid; ansp = pos; l = mid + 1; } else r = mid-1; } if(ans == -1) printf("none\n"); else printf("%d %d\n",ans,ansp-1); } return 0; }