HDU-4821 String
Given a string S and two integers L and M, we consider a substring of S as “recoverable” if and only if
(i) It is of length M*L;
(ii) It can be constructed by concatenating M “diversified” substrings of S, where each of these substrings has length L; two strings are considered as “diversified” if they don’t have the same character for every position.
Two substrings of S are considered as “different” if they are cut from different part of S. For example, string “aa” has 3 different substrings “aa”, “a” and “a”.
Your task is to calculate the number of different “recoverable” substrings of S.
思路
首先求出所有前缀的哈希值。
可以考虑枚举起始位置，然后依次往后查长为 $l$ 的子串的哈希值是否出现过，这个可以采用 map 来实现。
这样的话复杂度大约是 $O(n^2)$ ，显然是过不了本题的。
考虑采用类似于滑动窗口的策略，枚举起始位置后，每次去头添尾，这样优化后复杂度大概是 $O(n)$ ，可以通过本题。
本题对于 map 的利用较为巧妙。
代码
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 100010
using namespace std;
inline ll read() {
ll w=1,x=0;
char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return w*x;
}
const ull PP=131;
int n,m,l;
char s[N];
ull H[N],P[N];
ull get_hash(int l,int r) {
return H[r]-H[l-1]*P[r-l+1];
}
void init() {
n=strlen(s+1);
P[0]=1;
for(int i=1;i<=n;i++) P[i]=P[i-1]*PP;
for(int i=1;i<=n;i++) H[i]=H[i-1]*PP+s[i];
}
int main() {
while(~scanf("%d %d",&m,&l)) {
scanf("%s",s+1);
init();
int ans=0;
for(int i=1;i<=l&&i+m*l-1<=n;i++) {
map<ull,int> vh;
for(int j=i;j+l-1<=i+m*l-1;j+=l) vh[get_hash(j,j+l-1)]++;
if(vh.size()==m) ans++;
for(int j=i+m*l;j+l-1<=n;j+=l) {
ull nxt=get_hash(j,j+l-1);
vh[nxt]++;
ull pre=get_hash(j-m*l,j-m*l+l-1);
vh[pre]--;
if(!vh[pre]) vh.erase(pre);
if(vh.size()==m) ans++;
}
}
printf("%d\n",ans);
}
system("pause");
return 0;
}HDU-4080 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个样例）。
思路
显然可以二分答案。
首先预处理出所有前缀的哈希值。
然后开始对长度进行二分，利用 map 进行计数，若某一字符串的数量大于等于 $m$ 则返回 true ，否则 false 。
二分过程中记录位置即可，这样记录的就是最后一个的位置。
时间复杂度 $O(n\log n)$ （$n$ 为字符串长度）
代码
很是奇怪。
HDUOJ 交了能过， Vjudge 交了 TLE 。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 40010
using namespace std;
inline ll read() {
ll w=1,x=0;
char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return w*x;
}
const ull PP=131;
ll m,n,pos;
char s[N];
ull P[N],H[N];
ull get_hash(int L,int R) {
return H[R]-H[L-1]*P[R-L+1];
}
bool check(int x) {
map<ull,int> cnt;
bool flag=false;
for(int i=0;i+x-1<n;i++) {
ull now=get_hash(i,i+x-1);
cnt[now]++;
if(cnt[now]>=m) {
flag=true;
pos=i;
}
}
return flag;
}
void init() {
P[0]=1;
for(int i=1;i<=40000;i++) P[i]=P[i-1]*PP;
}
int main() {
init();
m=read();
while(m) {
scanf("%s",s);
n=strlen(s);
H[0]=s[0];
for(int i=1;i<n;i++) H[i]=H[i-1]*PP+s[i];
int l=0,r=n;
if(!check(1)) printf("none\n");
else {
while(l<r) {
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
if(!l) printf("none\n");
else printf("%d %d\n",l,pos);
}
m=read();
}
system("pause");
return 0;
}
