白兔的字符串（哈希）

白兔的字符串（哈希）

闲来无事学了下哈希，感觉上就是加密然后映射，下面直接上题目。
链接：https://ac.nowcoder.com/acm/problem/15253

题目描述

白兔有一个字符串T。白云有若干个字符串S1,S2…Sn。 白兔想知道，对于白云的每一个字符串，它有多少个子串是和T循环同构的。 提示：对于一个字符串a，每次把a的第一个字符移动到最后一个，如果操作若干次后能够得到字符串b，则a和b循环同构。 所有字符都是小写英文字母
输入描述:
第一行一个字符串T（|T|<=10^6）
第二行一个正整数n (n<=1000)
接下来n行为S1~Sn (|S1|+|S2|+…+|Sn|<=10^{7)，max(|S1|,|S2|,|S3|,|S4|,…|Sn|)<=10}6
输出描述:
输出n行表示每个串的答案

示例1

输入
abab
2
abababab
ababcbaba
输出
5
2

思路：将原先的字符串的所有循环同构的哈希值保存，然后每个查询就是直接查找是否存在该哈希值。我第一遍写的时候没注意会爆long long的情况，所以哈希值出现负的了，这里我们用unsigned long long就不会有这种情况了。

代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<map>
#include<set>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ll;//我只是懒得把下面的ll都改了，不要学我，还是用ull
typedef pair<int,int>P;
const int MAX_N=2000000+5;
const int INF=0x7fffffff;
const int inf=500000;
const double EPS=1e-6;
const ll base=123;
const ll mod=100007;
char s[MAX_N];
ll has[MAX_N];
ll h[MAX_N];
ll vis[MAX_N];
int viss[mod+5];
int pos=0;
struct node
{
   
    ll to;
    int next;
}rode[MAX_N];
void add(ll x)
{
   
    int xx=(int)(x%mod);
    rode[pos].to=x;
    rode[pos].next=viss[xx];
    viss[xx]=pos++;
}
int Find(ll x)
{
   
    int xx=(int)(x%mod);
    for(int i=viss[xx];i!=-1;i=rode[i].next)
    {
   
        if(rode[i].to==x)
            return 1;
    }
    return 0;

}
int main (void)
{
   
    memset(viss,-1,sizeof(viss));
    scanf("%s",s+1);
    int len=strlen(s+1);
    h[0]=(ll)1;
    int i;
    for(i=1;i<=2*len;i++)
    {
   
        h[i]=h[i-1]*base;
    }
    for(i=1;i<=len;i++)
    {
   
        s[len+i]=s[i];
    }
    for(i=1;i<=2*len;i++)
    {
   
        has[i]=base*has[i-1]+s[i]-'a';
        if(i>=len) add(has[i]-has[i-len]*h[len]);
    }

    int n;
    scanf("%d",&n);
    while(n--)
    {
   
        scanf("%s",s+1);
        int ans=0;
        has[0]=(ll)0;
        int l=strlen(s+1);
        for(i=1;i<=l;i++)
        {
   
            has[i]=has[i-1]*base+s[i]-'a';
            if(i>=len)
                ans+=Find(has[i]-has[i-len]*h[len]);
        }
        cout<<ans<<endl;
    }
}