XTU，C语言，String Hash

XTU，C语言，String Hash 题目描述

把字符串进行Hash，来判断字符串是否相等是一种很常见的技术。 对一个只含英文小写字母字符串进行Hash，一种比较简单的方法是把字符串看成一个26进制的数，a~z分别表示0~25，获得这个值后对某个素数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

这道题直接来做的的话一定会超时的，在这里，我们可以采用 秦九韶算法。

一元n次的多项式求值需要经过(n+1)*n/2次乘法和n次加法，而秦九韶算法只需要n次乘法和n次加法。见下：

#include 
#include 
#define p 1000000007
int main() 
{
    char str[1005];
    int len,i;
    long long sum;
    while(scanf("%s",str)!=EOF)
    {
        len = strlen(str),sum = 1;
        for(i = 0;i < len;i++)
        {
            sum *= 26;
            sum += str[i]-97;
            sum %= p;
        }
        printf("%lldn",sum);
    }
    return 0;
}