ZOJ - 4110 Strings in the Pocket （manacher马拉车 ）

BaoBao has just found two strings  and  in his left pocket, where  indicates the -th character in string , and  indicates the -th character in string .

As BaoBao is bored, he decides to select a substring of  and reverse it. Formally speaking, he can select two integers  and  such that  and change the string to .

In how many ways can BaoBao change  to  using the above operation exactly once? Let  be an operation which reverses the substring , and  be an operation which reverses the substring . These two operations are considered different, if  or .

Input

There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:

The first line contains a string  (), while the second line contains another string  (). Both strings are composed of lower-cased English letters.

It's guaranteed that the sum of  of all test cases will not exceed .

Output

For each test case output one line containing one integer, indicating the answer.

Sample Input

2 abcbcdcbd abcdcbcbd abc abc

Sample Output

3 3

Hint

For the first sample test case, BaoBao can do one of the following three operations: (2, 8), (3, 7) or (4, 6).

For the second sample test case, BaoBao can do one of the following three operations: (1, 1), (2, 2) or (3, 3).

题意：找出 t 串中的子串 通过翻转这个子串使得 t 串与 s 串相同，然后 t 中计算所有符合要求的子串个数。

思路：分为两种情况 t == s 和  t != s 

（1） t == s ：求出 t 中所有的回文字符串的个数，用马拉车求出以每一位为中心的最长回文串长度除以 2 就是 以每一位为中心的回文字符串的个数。还要加上单个字符的情况，个数为字符串的长度。

（2）t != s ：首先判断是否可以通过翻转成为相同的字符串，然后在翻转字符串的两侧延申，能够延伸几个就是结果。

#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<math.h> #include<string> #include<map> #include<vector> #define ll long long using namespace std; const ll inf=1e18; const ll MOD=1e9+7; const int maxn=2e6+10; char s[2*maxn],t[2*maxn]; char ma[2*maxn]; int mp[maxn*2]; void 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,id=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; } } } int main(){ int n; scanf("%d",&n); while(n--){ scanf("%s",s); scanf("%s",t); if(strlen(s)!=strlen(t)){printf("0\n");continue;} int len=strlen(s); if(strcmp(s,t)==0){ ll ans=0; manacher(t,len); for(int i=0;i<2*len+2;i++){ ans+=(mp[i]-1)/2; } printf("%lld\n",ans+len); }else{ int l=0,r=len-1; while(s[l]==t[l])l++; while(s[r]==t[r])r--; if(r<=l){ printf("0\n"); }else{ int el=r,er=l; while(s[l]==t[r]&&l<el&&r>er){ l++; r--; } if(l==el&&r==er){ int ans=1; l=er-1;r=el+1; while(l>=0&&r<len&&s[l]==s[r]&&t[l]==t[r]){ l--;r++;ans++; } printf("%d\n",ans); } else{ printf("0\n"); } } } } }