XTU OJ String Hash
发布时间
阅读量：
阅读量
String Hash
题目描述
把字符串进行Hash，来判断字符串是否相等是一种很常见的技术。 对一个只含英文小写字母字符串进行Hash，一种比较简单的方法是把字符串看成一个26进制的数，az分别表示025，获得这个值后对某个素数p取模。但是因为a是0，所以"abc"和"bc"的Hash值肯定是一样的，为了解决这个问题，我们假定在字符串前加入字符b（即26进制数最高位为1）比如p=11，字符串"abc",相当于26进制数"1012"，所以对应的十进制数为17604，所以哈希值为4。
我们假定p=1000000007，请将给定的字符串给出对应的hash值。
输入
存在多个样例。每行一个只含英文小写字母的字符串，长度不超过1000个字符。
输出
每行输出一个样例的结果
样例输入
abc
bc
abcdefghijklmnopqrstuvwxyz
样例输出
17604
704
115471061
解决思路：首先需要将输入字符串的每一位代表的数码存储起来。然后将其转换成10进制数，并进行取模运算。需要注意的是，输入的字符串可能会非常长（可能导致数据溢出问题），因此需要在计算过程中提前执行取模运算。
#define M 1000000007
#include<stdio.h>
#include<string.h>
int main()
{
int i;
char str[1001];
long long int a[1001]={0};
a[0]=1;
for(i=1;i<=1001;i++)
{
a[i]=(a[i-1]*26)%M;//位权 ，在这取模防止炸数据
}
while(scanf("%s",str)!=EOF)
{
int len=strlen(str);
long long ans=a[len];//因为得到的26进制数的最高位恒为‘1’转化成10进制即为1*a[len]
for(i=1;i<=len;i++)//len-i:对于a[i]i越大位权越大，len-i越来越小
{
ans+=(a[len-i]*(str[i-1]-97)%M);//str[i-1]-97代表每一位上的数码0，1，2...
ans%=M;//模的运算法则：(x+y)%M=(x%M+y%M)%M;
}
printf("%lld\n",ans);
}
return0;
}全部评论 (0)
还没有任何评论哟~