hdu 5782 Cycle(KMP+hash)

题目链接：hdu 5782 Cycle

题意：

给出两个字符串，判断他们每一个前缀是否循环同构，循环同构的意思就是，字符串首位相接拼成一个环，两个环通过旋转可以相等。

题解：

传送门

#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define F(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
typedef unsigned long long ull;

const int N=1e4+7;

struct string_hash{
    const static int seed=1331;
    static ull b[N];
    int len;ull h[N];
    inline int idx(char x){return x-'a'+1;}
    static void init(){b[0]=1;F(i,1,N-1)b[i]=b[i-1]*seed;}
    void ins(char *s)
    {
        len=strlen(s+1);
        F(i,1,len)h[i]=h[i-1]*seed+idx(s[i]);
    }
    inline ull ask(int l,int r){return h[r]-b[r-l+1]*h[l-1];}
}a[2];
ull string_hash::b[N];

char sa[N],sb[N];
int nxt[N],ans[N];

int check(int n,int m,int op)
{
    if(n==m)return 1;
    return a[op].ask(m+1,n)==a[op^1].ask(1,n-m);
}

void KMP(int n, char*a, int m, char*b,int op) {
    int i, j;
    for (nxt[0] = j = -1, i = 1; i < n; nxt[i++] = j) {
        while (~j&&a[j + 1] != a[i])j = nxt[j];
        if (a[j + 1] == a[i])j++;
    }
    for (j = -1, i = 0; i < m; i++) {
        while (~j&&a[j + 1] != b[i])j = nxt[j];
        if (a[j + 1] == b[i])
        {
            j++;
            if(!ans[i])ans[i]=check(i+1,j+1,op);
        }
        if (j == n - 1) j = nxt[j];
    }
}

int main(){
    string_hash::init();
    while(~scanf("%s%s",sa+1,sb+1))
    {
        a[0].ins(sa),a[1].ins(sb);
        mst(ans,0);
        KMP(a[0].len,sa+1,a[0].len,sb+1,0);
        KMP(a[0].len,sb+1,a[0].len,sa+1,1);
        ans[a[0].len+1]=0;
        F(i,0,a[0].len-1)printf("%d",ans[i]);
        puts("");
    }
    return 0;
}