题意:给你2个串,让你判断2个字符串的前缀是否满足首尾连接形成的环是不是一样的。
思路:我们需要提前知道的是满足条件的前缀一定满足 strA = str1 + str2, strB = str2 + str1。然后我们先求出其中的一个的KMP,然后去匹配,那么我们匹配过程中一定会有一个公共长度j,那么我们利用好j这一段再加上判断剩下的部分是不是相等的就好了,那么这一段就可以相当于str2,然后我们再用带有顺序的hash技术,将其他的映射出来就好了,然后用的时候直接乘上当前值的进制值就好了,就是有一个需要移一下位才能进行同等级的比较。
#include<bits/stdc++.h>
using namespace std; const int maxn = 1e4 + ;
const int base = ; long long p[maxn], hass[][maxn];
int n, nex[maxn];
char A[maxn], B[maxn];
bool ans[maxn]; long long getVal(int t, int l, int r){
return hass[t][r] - hass[t][l - ] * p[r - l + ];
} bool check(int t, int a, int b){
if(a == b) return true;
return getVal(t, a + , b) == getVal(t^, , b - a);
} void kmp(int al, char a[], int bl, char b[], int t){
int i, j;
for(nex[] = j = , i = ; i <= al; nex[i ++] = j){
while(j && a[j + ] != a[i]) j = nex[j];
if(a[j + ] == a[i]) j ++;
} for(j = , i = ; i <= bl; i ++){
while(j && a[j + ] != b[i]) j = nex[j];
if(a[j + ] == b[i]){
j ++;
if(!ans[i]) ans[i] = check(t, j, i);
}
if(j == al) j = nex[j];
}
} int main(){
//freopen("data", "r", stdin);
for(int i = p[] = ; i < maxn; i ++) p[i] = p[i - ] * base;
while(~scanf(" %s %s", A + , B + )){
int len = strlen(A + );
for(int i = ; i <= len; i ++){
ans[i] = false;
hass[][i] = hass[][i - ] * base + A[i];
hass[][i] = hass[][i - ] * base + B[i];
}
kmp(len, A, len, B, );
kmp(len, B, len, A, );
for(int i = ; i <= len; i++ ) printf("%c", ""[ans[i]]);printf("\n");
}
return ;
}