题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=4821
解题报告：搞了很久，总算搞出来了，还是参考了一下网上的解法，的确很巧，和上次湘潭的比赛中的一个求平方和的题目思路很类似。
首先说一下hash，简单来说就是y = hash(x)，有很多函数，可以参考这里：https://www.byvoid.com/blog/string-hash-compare/
然后，我用的是这个：写法简单，而且重复的可能较小。
// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
unsigned int seed = ; // 31 131 1313 13131 131313 etc..
unsigned int hash = ; while (*str)
{
hash = hash * seed + (*str++);
} return (hash & 0x7FFFFFFF);
}
然后回到这个题目：
3W,4RE,3TLE,首先wa的原因：循环次数少了一，<=slen,超时没办法，只能优化了。
下面是没有优化的代码，每个子串求一下hash.
/*
#include <cstdio>
#include <cstring>
#include <string> using namespace std; const int inf = 2000000; bool t[2000000];
int Hash[100005]; long long myhash(char *str)
{
int seed = 31;
long long hash = 0;
while (*str)
hash =( hash * seed + (*str++)-'a' + 1) %inf ;
return hash;
} int main()
{
int m,l;
while(scanf("%d%d",&m,&l)!=EOF)
{
char str[100005];
scanf("%s",str);
int len = strlen(str);
int ans = 0; int k = 0;
for(int i=0; i+m<len; i++)
{
char temp[100005];
for(int j=0; j<l; j++)
temp[j] = str[i+k*m+j];
temp[l] = '\0';
long long hashs = myhash(temp);
Hash[i+k*m] = myhash()
} for(int i=0; i<l&&i+m*l<=len; i++)
{
memset(t,false,sizeof(t));
bool flag = true;
for(int k = 0; k<m; k++)
{
char temp[100005];
for(int j=0; j<l; j++)
temp[j] = str[i+k*m+j];
temp[l] = '\0';
long long hashs = myhash(temp);
if(t[hashs])
{
flag = false;
break;
}
t[hashs] = true;
}
if(flag) ans++;
}
printf("%d\n",ans);
}
return 0;
} */
优化方案。上图比较好！！！
优化的位置就是成段删掉，成段添加。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map> using namespace std;
const int MAXN = ;
const unsigned long long base = ; unsigned long long nbase[MAXN],Hash[MAXN];
int n,len,ans,slen;
char str[MAXN];
map<unsigned long long, int> mp; int main()
{
unsigned long long tmp;
nbase[] = ;
for (int i = ; i <= MAXN; i++)
nbase[i] = nbase[i-] * base; while (scanf("%d%d", &n, &len) != EOF)
{
scanf("%s", str);
slen = strlen(str);
Hash[slen] = ;
for (int i = slen-; i >= ; i--)
Hash[i] = Hash[i+]*base+str[i]-'a'+; ans = ;
for (int i = ; i < len && i+n*len <= slen; i++)
{
mp.clear();
for (int j = i; j < i+n*len; j += len)
{
tmp = Hash[j] - Hash[j+len]*nbase[len];
mp[tmp]++;
}
if (mp.size() == n)
ans++;
for (int j = i+n*len; j+len <= slen; j += len)
{
tmp = Hash[j-n*len] - Hash[j-(n-)*len]*nbase[len];
mp[tmp]--;
if (mp[tmp] == )
mp.erase(tmp);
tmp = Hash[j] - Hash[j+len]*nbase[len];
mp[tmp]++;
if (mp.size() == n)
ans++;
}
}
printf("%d\n", ans);
}
return ;
}