还是一道很综合的 string 练手题。
先来分析一下,将 \(B\) 按照答案分成三段,三段与 \(A\) 都有什么关系。
第一段:\(A\) 的一个子串。
第二段:\(A\) 的一段后缀翻转。
第三段:\(A\) 的一段前缀翻转。
我们大概率是要枚举其中一个的,其中第三段都能用 \(A,B\) 的前后缀表示,考虑枚举它,也就是枚举 \(i\)。
下令 \(len\) 为 \(|A|\)。
然后考虑怎样处理剩下的。发现此时第一段在 \(A,B\) 中的左端点都已经确定(分别是 \(i+1,0\))。于是可以考虑求出 \(L=\operatorname{lcp}(A[i+1,len-1],B[0,len-1])\)。剩下的要求就是 \(\exists j\le L,A[i+j+1,len-1]=R(B[j,len-i-2])\)。这可以看作一个和上面类似的东西,但是前面那个可以用拓展 kmp 求的东西和 kmp 是相关联的。可以得到这个式子等价于 \(\operatorname{lcp}(A[i+1,len-1],B[0,len-1])+\operatorname{maxpos}(len-i-2)\ge len-i-1\)。其中 \(\operatorname{maxpos}(x)\) 为以 \(R(A)\) 为模式串,\(B\) 为文本串做 kmp,遍历到文本串第 \(x\) 位时,模式串匹配了多长。于是做完了。
但是我没用 exkmp,用的是字符串 hash。
code:
点击查看代码
const int base[2]={13331,131313},mod[2]={(int)1e9+9,469762049};
int n,m,c[207][2],fail[N],pre[N],suf[N],f[N][2],g[N][2],pw[N][2];
char s[N],t[N],r[N];
mt19937 rnd(time(0));
void readStr(char *s,int &n){
char c=gc();
while(c<32||c>126)c=gc();
while(c>=32&&c<=126)s[++n]=c,c=gc();
}
il pair<ll,ll> getHashf(int l,int r){
if(l>r)return Mp(0,0);
return Mp((f[r][0]-1ll*f[l-1][0]*pw[r-l+1][0]%mod[0]+mod[0])%mod[0],(f[r][1]-1ll*f[l-1][1]*pw[r-l+1][1]%mod[1]+mod[1])%mod[1]);
}
il pair<ll,ll> getHashg(int l,int r){
if(l>r)return Mp(0,0);
return Mp((g[r][0]-1ll*g[l-1][0]*pw[r-l+1][0]%mod[0]+mod[0])%mod[0],(g[r][1]-1ll*g[l-1][1]*pw[r-l+1][1]%mod[1]+mod[1])%mod[1]);
}
void Yorushika(){
readStr(s,n),readStr(t,m);
if(n!=m){puts("-1 -1");return;}
rep(i,1,150)c[i][0]=c[i][1]=i;
pw[0][0]=pw[0][1]=1;
rep(i,1,n)rep(j,0,1){
f[i][j]=(1ll*f[i-1][j]*base[j]+c[s[i]][j])%mod[j];
g[i][j]=(1ll*g[i-1][j]*base[j]+c[t[i]][j])%mod[j];
pw[i][j]=1ll*pw[i-1][j]*base[j]%mod[j];
}
rep(i,1,n){
int l=0,r=n-i+1;
pre[i]=0;
while(l<=r){
int mid=(l+r)>>1;
if(getHashf(i,i+mid-1)==getHashg(1,mid))l=(pre[i]=mid)+1;
else r=mid-1;
}
}
rep(i,1,n)r[i]=s[n-i+1];
rep(i,2,n){
int &j=(fail[i]=fail[i-1]);
while(j&&r[i]!=r[j+1])j=fail[j];
j+=r[i]==r[j+1];
}
rep(i,1,n){
int &j=(suf[i]=suf[i-1]);
while(j&&t[i]!=r[j+1])j=fail[j];
j+=t[i]==r[j+1];
}
int p=0;
while(p<n&&s[p+1]==t[n-p])p++;
drep(i,min(p,n-1),1){
if(s[i]!=t[n-i+1])break;
if(pre[i+1]+suf[n-i]>=n-i)return printf("%d %d\n",i-1,n-suf[n-i]),void();
}
puts("-1 -1");
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}