思路：给字符串做一个映射，两个元素相同，则他们的hash值必定相同。

注意：hash表必须是unsigned int类型，保证每个映射都是正数。

 

例题：

Description

给出两个字符串W和T，求T中有几个W子串。

Input

第一行为数据数.

每组数据有两行W和T，表示模式串和原始串.

Output

对每组数据，每行一个数，表示匹配数.

Sample Input

3

BAPC

BAPC

AZA

AZAZAZA

VERDI

AVERDXIVYERDIAN

Sample Output

1

3

0

 

代码：

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn = 1200;typedef unsigned long long ULL;ULL pre[maxn],hs[maxn],base=133; //base基数设置为素数 char s1[maxn],s2[maxn];void Init(){    pre[0]=1;    for(int i=1;i