这个题数据又小又水。一个点N=5,M=24,另一个点N=7,M=8。字符串长度<=1000000，随便乱做都可以过。
/*
Sol:由于本题已告诉大家，子串个数<=1000000,
所以我们只需要将字符串hash成一个数字
将它们放到一个数组中，接下来是去重的工作，
于是可以快排，这样数字就有序了。
接下来可以进行去重工作
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define P 29
#define maxn 1000010
using namespace std;
unsigned long long n,c,len,p[maxn],ha[maxn],tot,hashh[maxn],ans;
char s[maxn];
void Get_p()
{
p[0]=1;
for(int i=1;i<=n;i++)
p[i]=p[i-1]*P;
}
void Get_ha()
{
len=strlen(s+1);
for(int i=1;i<=len;i++)
ha[i]=ha[i-1]*P+s[i]-'a';
}
unsigned Query(int l,int r)
{
return ha[r]-ha[l-1]*p[r-l+1];
}
void Solve()
{
for(int l=1;l+n-1<=len;l++)
{
int r=l+n-1;
hashh[++tot]=Query(l,r);
}
sort(hashh+1,hashh+1+tot);
for(int i=1;i<=tot;i++)
if(hashh[i]!=hashh[i-1])ans++;
}
int main()
{
scanf("%d%d%s",&n,&c,s+1);
Get_p();Get_ha();Solve();
printf("%d
",ans);
return 0;
}
/*
解析:由于取出来的子串长度<=7,字符的种类<=24,也就意识着
我们将字符串hash出来的数值不会太大,是<=24^7，于是可以
直接开一个bool数组来进行去重工作
*/
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
using namespace std;
int n,nc,num=0,ans=0;
string s;
bool Vis[1005];
int V[1005];
bool Hash[16000005];
int main()
{
cin>>n>>nc;
cin>>s;
int len=s.length();
for(int i=0;i<len;++i)
{
if(!Vis[s[i]])
{
Vis[s[i]]=true;
V[s[i]]=++num;
}
}
for(int i=0;i<=len-n;++i)
{
int sum=0;
for(int j=i;j<i+n;++j)
{
sum+=nc*sum+V[s[j]];
}
if(!Hash[sum])
{
ans++;
Hash[sum]=true;
}
}
cout<<ans<<endl;
return 0;
}
如果hash出来的数字很大，则只能用hash，或用set,或map进行查重了(用这两个就是好写点，但多了个Log)
上题也可以这样做,但明显速度慢了许多。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
map<char,int>q;
map<ull,int>p;
int n,m,len,noww=0,ans=0;
char s[20000000];
ull power[1000000],sum[1000000];
int get(int l,int r)
{
return sum[r]-sum[l-1]*power[r-l+1];
}
int main()
{
scanf("%d%d%s",&n,&m,s+1);
len=strlen(s+1);
power[0]=1;
for(int i=1;i<=len;i++)
{
power[i]=power[i-1]*m;
if(q[s[i]]==0)q[s[i]]=++noww;
}
for(int i=1;i<=len;i++)
sum[i]=sum[i-1]*m+q[s[i]];
for(int i=1;i<=len-n+1;i++)
{
ull a=get(i,i+n-1);
if(p[a]==0)p[a]=1,ans++;
}
printf("%d
",ans);
return 0;
}
对于一些精心构造过的数据，则可用双hash