Oulipo 【POJ - 3461】【双值哈希】

题目链接

题意：给你两个字符串，前一个是小字符串，后一个是大的字符串，问你，大的字符串中有几组可以与小的字符串相等的子字符串。

此题其实不用双值哈希好像也可以的，但为了确保A就敲了个双值哈希，我们想把字符串的形式用数的值来表示，那么，我们可以用到哈希来转换它，而双值哈希的目的就是为了减少被Hack的可能性。

完整代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ull Hash=1e8+7, Hash2=1e8+5;
const int maxN=1e4+5;
char a[maxN], b[maxN*100];
ll al, bl, ans;
void solve()
{
    if(al>bl) return;
    ull hash_a=0, hash_b=0, hash_a_1=0, hash_b_1=0, Basic=1, Basic2=1;;
    for(int i=0; i<al; i++)
    {
        Basic*=Hash;
        Basic2*=Hash2;
        hash_a=hash_a*Hash+a[i];    hash_a_1=hash_a_1*Hash2+a[i];
        hash_b=hash_b*Hash+b[i];    hash_b_1=hash_b_1*Hash2+b[i];
    }
    for(int i=0; i+al<=bl; i++)
    {
        if(hash_a==hash_b && hash_a_1==hash_b_1) ans++;
        hash_b=hash_b*Hash-Basic*b[i]+b[i+al];
        hash_b_1=hash_b_1*Hash2-Basic2*b[i]+b[i+al];
    }
}
int main()
{
    int T;  scanf("%d", &T);
    while(T--)
    {
        ans=0;
        getchar();
        scanf("%s", a);
        getchar();
        scanf("%s", b);
        al=strlen(a);   bl=strlen(b);
        solve();
        printf("%lld\n", ans);
    }
    return 0;
}