K - Strings in the Pocket
&:给你两个串 s 和 t , 问能否翻转 s 串的子串让 s 和 t 一样,问可以翻转的种类有多少个?
&:如果两个字符串相同时用 Manacher 求出回文串的个数,这里用回文数会爆掉内存。如果不同的话,找到那部分串,以这个串为中心向两边扩展 ,如果两边是回文串,那就 ans ++。
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = (a); i < (b); i ++)
#define MM(x) memset(x,0,sizeof(x))
#define ll long long
using namespace std;
const int maxn = 2e6+5;
char s[maxn],t[maxn];
char Ma[maxn*2];
int Mp[maxn*2];
ll Manacher(char s[], int len)
{
int l = 0;
Ma[l++] = '$';
Ma[l++] = '#';
for(int i = 0; i < len; i ++)
{
Ma[l++] = s[i];
Ma[l++] = '#';
}
Ma[l] = 0;
int mx = 0;
int id = 0;
ll res = 0;
for(int i = 0; i < l; i ++)
{
Mp[i] = mx > i ? min(Mp[2 * id - i], mx - i) : 1;
while(Ma[i + Mp[i]] == Ma[i - Mp[i]])Mp[i]++;
if(i + Mp[i] > mx)
{
mx = i + Mp[i];
id = i;
}
}
for(int i = 0; i < l; i ++)
res += Mp[i] / 2;
return res;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int l,r;
l = r = -1;
scanf("%s%s",s,t);
int len = strlen(s);
for(int i = 0; i < len; i ++)
{
if(s[i] != t[i]){
l = i;
break;
}
}
for(int i = len - 1; i >= 0; i --)
{
if(s[i] != t[i])
{
r = i;
break;
}
}
if(l == r && r == -1){
printf("%lld\n",Manacher(s,len));
}
else {
int flag = 0;
for(int i = l; i <= r; i ++)
{
if(s[i] != t[r - i + l])
{
flag = 1;
printf("0\n");
break;
}
}
if(flag == 0)
{
ll sum = 1;
l --;
r ++;
// cout << l <<" " << r <<endl;
while(l >= 0 && r <= len - 1)
{
if(s[l] == s[r])
{
l --;
r ++;
sum ++;
}
else break;
}
printf("%lld\n",sum);
}
}
}
return 0;
}