[字符串操作][基本練習]OI練習題：字符串哈希

        字符串哈希(stringhash.cpp/pas/c)

字符串哈希是一種非常好用的算法，它可以將一個字符串用一個整數來表示（儘管有時候會發生衝突），這是非常方便的.

現在小H拿着一些字符串來找你，希望你能幫她把這些字符串按照給定的規則轉換成哈希值..

一個長度爲n的字符串c1,c2,c3..cn-1,cn的哈希值=它的子串c1,c2,c3..cn-1的哈希值乘以一個常數Seed，再加上cn的ASCII值，

最後對一個整數2147483647求 “和” 運算的結果（“和”爲位運算中的和，分別是Pascal中的and和C/C++中的&）

請注意，空串的哈希值爲0

輸入格式：

有N組數據

第一行是一個整數N

接下來有若干組數據，每個數據第一行是一個數len（len<=20），表示字符串的長度

下面一行有一個字符串和一個整數Seed，用一個空格隔開，字符串中只可能包含'a'..'z','1'..'9','A'..'Z'

輸出格式：

共N行，每行一個整數即爲對應數據的哈希值

樣例輸入：

1

6

yznJS1 131

樣例輸出：

1306619859

數據範圍：

N<=10000

Seed<=131

其他如題。

by pom

【分析】

直接模擬即可，注意位運算的and操作(&)以及空字符串的情況。

【代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN=0x7fffffff;
int main()
{
    freopen("stringhash.in","r",stdin);
    freopen("stringhash.out","w",stdout);
    int N;
    cin>>N;
    int Len;
    long long Seed;
    char str[21];
    long long Hash[21];
    for (int i=1;i<=N;i++)
    {
        cin>>Len;
        if(Len==0)
        {
            cin>>Seed;
            cout<<0<<endl;
            continue;
        }
        memset(str,'\0',21);
        cin>>str;
        cin>>Seed;
       
        Hash[0]=str[0];
        for (int j=1;j<Len;j++)
        {
            Hash[j]=Hash[j-1]*Seed+str[j];
            Hash[j]&=MAXN;
        }
        cout<<Hash[Len-1]<<endl;
    }
    return 0;
}