Strings in the Pocket ZOJ - 4110

本文主要是介绍Strings in the Pocket ZOJ - 4110，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4110

先看两个字符串是否相等  若相等则直接用马拉车求回文半径即可

否则 找出l和r来 满足[0,l-1]与[r+1,n-1]内两字符串相等 然后看两字符串[l,r]内是否完全相反 若不完全相反 即翻转后仍无法相等则输出0 否则就以(l+r)/2即不相等子串的中心 左右边界同时向外拓展

主要是理解为什么要以不相等子串的中心为中心 假设中心换作其他位置

lef1 | rgt1

lef2 | rgt2 

其中lef1与lef2是不相等子串 rgt1与rgt2 是相等后缀 若翻转后相等 则有rev(lef1)=rgt2 rev(rgt1)=lef2

又因为rgt1=rgt2 所以rev(lef1)=rgt1=rev(lef2) 得lef1=lef2 与假设矛盾 所以必须以不相等子串的中心为中心

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e6+10;char s[2*maxn],t[maxn];
int book[2*maxn];
int n,l;ll manacher()
{ll res;int i,j,p,r;l=2*n+1;for(i=0;i<n;i++){s[2*i]='*',s[2*i+1]=t[i];}s[2*n]='*',s[l]='\0';p=0,r=0;for(i=0;i<l;i++){if(i<r) book[i]=min(book[2*p-i],r-i);else book[i]=1;while(0<=i-book[i]&&i+book[i]<l&&s[i-book[i]]==s[i+book[i]]){book[i]++;}if(r<i+book[i]){p=i,r=i+book[i];}}res=0;for(i=0;i<l;i++){res+=ll((book[i]-1+i%2)/2);}return res;
}int main()
{int tt,i,j,pl,pr,ans;scanf("%d",&tt);while(tt--){scanf("%s%s",s,t);n=strlen(s),pl=-1;for(i=0;i<n;i++){if(s[i]!=t[i]){pl=i;break;}}for(i=n-1;i>=0;i--){if(s[i]!=t[i]){pr=i;break;}}if(pl==-1){printf("%lld\n",manacher());}else{for(i=pl,j=pr;i<=pr;i++,j--){if(s[i]!=t[j]){break;}}if(i==pr+1){ans=1,pl--,pr++;while(0<=pl&&pr<n&&s[pl]==s[pr]){ans++,pl--,pr++;}printf("%d\n",ans);}else printf("0\n");}}return 0;
}//aa

 

这篇关于Strings in the Pocket ZOJ - 4110的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---