此题堪称经典的hash啊。题目是给你一个字符串很长，给你子字符串的长度N和这个字符串中共有多少个不同的字符NC，求这个长的字符串有多少中长度为N的子字符串。
此题我已开始想的是map，不想超时。只能用这种方法。
在这个题上有一个技巧，就是由于题目没说字符串里面是什么字符，所以这里很巧妙的应用了ascll码作为数组下标变量。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 16000000
char s[maxn];
int a[10000];
int hash[maxn];
int main()
{
int N,NC,num=0,len,i,cnt=0,sum=0,j;
scanf("%d%d",&N,&NC);
scanf("%s",&s);
len=strlen(s);
for(i=0;i<len;i++)//ascll码作为下标
{
if(!a[s[i]])
a[s[i]]=++num;
}
for(i=0;i<len-N+1;i++)
{
sum=0;
for(j=i;j<i+N;j++)
sum+=sum*NC+a[s[j]];
if(!hash[sum])
{//hash表
cnt++;
hash[sum]=1;
}
}
printf("%d/n",cnt);
return 0;
}
此题让我想到了另外一题。
I. DNA序列检测(绿)
问题描述
给定一个长度为N的字符串S（字符集为ACTG）和Q个询问，每个询问为一个长度不超过10的字符串T（字符集同样为ACTG）。对于每个询问，你需要回答T是否是S的一个子串(substring)。
输入格式
输入文件的第一行包含两个整数N和Q，含义如上文所示。(N,Q <=1000000)
接下来的一行包含一个长度为N的字符串，表示S。
接下来的Q行每行包含一个长度不超过10的字符串T。
输出格式
对于每个询问，如果T是S的子串的话，输出Yes，否则输出No。
输入样例
10 3 ACTGTGTGAC ACT ACTT TGTG
输出样例
Yes No Yes
这两道题其实是一样的啊，如果当时我做过1200，这道题目就简单了，我当时还用KMP算法，bs！
代码：
- #include<stdio.h>
- #include<string.h>
- #include<math.h>
- char str[1000001];
- int w[1000001];
- int h[10000000];
- int main()
- {
- int m,n,i,j,t,k,sum;
- char s[11];
- scanf("%d%d",&m,&n);
- scanf("%s",str);
- t=0;
- memset(h,0,sizeof(h));
- for(i=0;i<m;i++)
- {
- if(str[i]=='A')
- w[i]=1;
- else if(str[i]=='C')
- w[i]=2;
- else if(str[i]=='T')
- w[i]=3;
- else if(str[i]=='G')
- w[i]=4;
- }
- for(i=0;i<m;i++)
- {
- t=0;
- for(j=0;j<10&&(i+j)<m;j++)
- {
- t=t*4+w[i+j];
- h[t]=1;
- }
- }
- for(i=0;i<n;i++)
- {
- memset(s,0,sizeof(s));
- scanf("%s",s);
- j=strlen(s);
- sum=0;
- for(k=j-1;k>=0;k--)
- {
- if(s[k]=='A')
- sum+=(int)pow(4.0,j-1-k);
- else if(s[k]=='C')
- sum+=(int)(2*pow(4.0,j-1-k));
- else if(s[k]=='T')
- sum+=(int)(3*pow(4.0,j-1-k));
- else if(s[k]=='G')
- sum+=(int)(4*pow(4.0,j-1-k));
- }
- if(h[sum]==1)
- printf("Yes/n");
- else
- printf("No/n");
- }
- return 0;
- }