首页 > 代码库 > Quicksearch1200_hash

Quicksearch1200_hash

2024-07-26 01:32:50   216人阅读

大致题意：

    给出两个数n,nc，并给出一个由nc种字符组成的字符串。求这个字符串中长度为n的子串有多少种。

 

大致思路：

裸哈希之，将长度为n的子串看作 n位的 nc进制数，将问题转化为共有多少种数字，从而确定是否重复

3 4

daababac

d = 3

a = 0

b = 1

c = 2

daa = 3 * 4 ^ 2 + 0 * 4 ^ 1 + 0 * 4 ^ 0 = 48

 

其实这里的测试用例4表示有四种字母，而实际上有3种，但是没有关系，对于最后求得的数字之和没有影响。

 

 

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int hash[30];bool loc[20000000];char str[1000000];int main(){    int n,m,cnt,sum,len,ans,i,j;    while(scanf("%d%d",&n,&m)!=EOF)	{        memset(loc,0,sizeof(loc));        memset(hash,0,sizeof(hash));        scanf("%s",str);        len=strlen(str);        cnt=1;        ans=0;        for(i=0;i+n<=len;i++)		{//起点            sum=0;            for(j=i;j<i+n;j++)			{                if(!hash[str[j]-‘a‘])//如果为0，那么将字母转换成数字。至于哪个数字大点，哪个数字小点无所谓。				{                    hash[str[j]-‘a‘]=cnt++;                }                sum*=m;//低位后到，高位先到。因此先把高位的乘以进制，再加上低位                sum+=hash[str[j]-‘a‘];            }            if(!loc[sum])			{                loc[sum]=1;                ans++;            }        }        printf("%d\n",ans);    }    return 0;}

 

　　

 

Quicksearch1200_hash


联系
我们