文章目录

[Strings in the Pocket](https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370505)题目大意解题思路代码

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]); //判断当前点超没超过mx else Len[i] = 1; //超过了就让他等于1，之后再进行查找 while (str[i + Len[i]] == str[i - Len[i]]) Len[i]++; //判断当前点是不是最长回文子串，不断的向右扩展 if (Len[i] + i > mx) {//更新mx mx = 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; }