2019年浙江省赛的题目,但是一直没补,正好又复习了下马拉车,趁热补上。
题目地址:https://vjudge.net/problem/ZOJ-4110
题目解释:
给出原串s,和新串t,问有多少种方案可以使s中在[l,r](l≤r)区间内的字符翻转之后能让s串变成t串
如s串和t串分别为:
abcbcdcbd
abcdcbcbd
三种方案:(2, 8), (3, 7) or (4, 6),故答案为3
解题思路:
- s串=t串:以每一个字母为中心的最长回文子串的长度的一半 总和即为答案(因为翻转之后和原串相同)
- s串!=t串:找到s串和t串不同的那段区间[l,r],如果s串中[l,r]区间内的字符翻转之后和t串那段区间的字符不同相同的话,那么方法数为0,否则,[l,r]区间向两边扩展,当然扩展的条件是左侧的字符和右侧的字符相等
ac代码:
#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <fstream>
const int maxn=3e6+10;
#define lowbit(x) (x&(-x))
typedef long long ll;
const ll mod=1e9+7;
using namespace std;
int leng,len[maxn],ans=0,l,r;
char t[maxn],s[maxn],news[maxn];
void init()
{
int k=0;
for(int i=0;i<leng;i++)
{
news[k++]='#';
news[k++]=s[i];
}
news[k++]='#';
leng=k;//实际长度,不是下标
}
int manacher()
{
init();
memset(len,0,sizeof(len));
int id=0,mx=0;
for(int i=0;i<leng;i++)//从第一个#开始
{
if(i<mx) len[i]=min(mx-i,len[2*id-i]);
else len[i]=1;
while((i-len[i])>=0 && (i+len[i])<leng && news[i-len[i]]==news[i+len[i]]) len[i]++;
if(len[i]+i>mx)
{
mx=len[i]+i;
id=i;
ans+=(len[i])/2;
}
}
return ans;
}
bool duichen()
{
for(int i=0;i<leng;i++)
{
if(s[i]!=t[i])
{
if(l==-1) l=i;//l只更新一次
r=i;
}
}
for(int i=0;i<=(r-l);i++)
{
if(s[l+i]!=t[r-i])//翻转之后不相同
return false;
}
return true;
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
int T;
cin>>T;
while(T--)
{
cin>>s>>t;
leng=strlen(s);
ans=0;l=r=-1;
if(strcmp(s,t)!=0)
{
if(duichen())
{
ans+=1;
for(int i=l-1,j=r+1;i>=0 && j<leng && s[i]==s[j];i++,j++)
ans++;
printf("%d\n",ans);
}
else printf("0\n");
}
else
{
manacher();
printf("%d\n",ans);
}
}
return 0;
}