Strings in the Pocket（马拉车）

Strings in the Pocket（马拉车）

文章目录

• [Strings in the Pocket]()
• • 题目大意
  • 解题思路
  • 代码

Strings in the Pocket

题目大意

一共T组测试数据，每组给出两个字符串，让你选择一个区间交换过后，两个字符串相同。输出方案数。

解题思路

可以分为三种情况
1，两个字符串有多个连续位置不同
2，只有一段连续位置不同。
3，完全相同
对于一，我们肯定不可能操作一次后使得两个字符串相同的
对于二，我们选取知道这段区间，看看通过转换这段区间的字符串后是否相同，如果相同，那么在加上这个区间向外扩相同的字符串的组数。
对于三，我们求出每个位置对应的最长回文串的长度和即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mx=4000100;int Len[mx];
char str[mx];
char s[mx],t[mx];
int len; 
ll manacher() {int mx = 0, id;//mx为最右边，id为中心点int maxx = 0;for (int i = 1; i < len; i++) {if (mx > i) Len[i] = min(mx - i, Len[2 * id - i]);//判断当前点超没超过mxelse Len[i] = 1; //超过了就让他等于1，之后再进行查找while (str[i + Len[i]] == str[i - Len[i]]) Len[i]++;//判断当前点是不是最长回文子串，不断的向右扩展if (Len[i] + i > mx) {//更新mxmx = Len[i] + i;id = i;//更新中间点maxx = max(maxx, Len[i]);//最长回文字串长度}}ll ans=0;for(int i=0;i<len;i++){ans+=Len[i]/2LL;}return ans;
}
void getstr() {//重定义字符串int k = 0;str[k++] = '@';//开头加个特殊字符防止越界for (int i = 0; i < len; i++) {str[k++] = '#';str[k++] = s[i];}str[k++] = '#';len = k;str[k] = 0;//字符串尾设置为0，防止越界
}bool check(int l,int r){for(int i=l,j=r;i<=r;i++,j--){if(s[i]!=t[j]) return 1;}return 0;
}int main(){ios::sync_with_stdio(0);int _;cin>>_;while(_--){cin>>s>>t;int l=-1,r=-1;len=strlen(s);int f=0;for(int i=0;i<len;i++){if(s[i]!=t[i]){if(l==-1) l=i;r=i;f=1;}}ll ans=0;if(f){//情况二的 不可能情况 if(check(l,r)) ans=0;else{// 情况二的可能情况	ans=1;for(int i=r+1,j=l-1;i<len&&j>=0;i++,j--){if(s[i]==t[j]) ans++;else break; }}}else{//情况三 getstr();ans=manacher();}cout<<ans<<"n";}return 0;
}