【2019浙江省赛 - K 】Strings in the Pocket（马拉车，思维）

题干：

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).

题目大意：

给你两个串s1和s2,可以翻转s1串的一个区间，只能翻转一次，,问有多少对l,r使得翻转后的s1串等于s2串

解题报告：

  当两串完全相同的时候就是马拉车，不同的时候就先两边往里扫到两串第一个不相同的位置，在第一个串往外扩，看能扩几次，答案就是多少。

注意无数细节，，，那个初始化（见注释）还有那个while(1)里面必须是if(l>=ed)就可以break了一开始写成了l>ed，，，WA了一上午难受难受。。。

其实不是细节多，，而是代码姿势不太对，，，还是太菜，，不过这么简单的一题比赛的时候没有开有点小亏。做网络同步赛打了三小时比赛水了7题，就去准备晚上给学弟讲课的PPT去了。。。这成绩对比了下，好像7题放现场赛也只是个铜（不过罚时较少可能是银？）。。不过这题是真不难。。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 4e6 + 5;
char s1[MAX],s2[MAX],str[MAX<<1];
int p[MAX<<1],top;
int manacher() {
	if(top == 0) return 0 ;
	int maxx = -1;
	int c = -1,r = -1;
	for(int i = 1; i<top; i++) {
		p[i] = r>i ? min(p[2*c-i],r-i) : 1;
		for(;str[i-p[i]] == str[i+p[i]];p[i]++);
		if(i+p[i] > r) {
			r = i+p[i];
			c=i;
		}
		maxx = max(maxx,p[i]);
		
	}
	return maxx-1;
}



int main()
{
	int t;
	cin>>t;
	while(t--) {
		scanf("%s%s",s1,s2);
		int len = strlen(s1);
		if(strcmp(s1,s2) != 0) {
			int st=-1,ed=len,l,r;//需要赋初值！！！ 
			int flag = 1;
			for(int i = 0; i<len; i++) {
				if(s1[i] == s2[i]) st = i;
				else break;
			}
			for(int i = len-1; i>=0; i--) {
				if(s1[i] == s2[i]) ed = i;
				else break;
			}
			l=st+1,r=ed-1;
			while(1) {
				if(l >= ed) break;
				if(s1[l] == s2[r]) l++,r--;
				else {flag = 0;break;	}
			}
			if(flag == 0) {puts("0");continue;		}
			l=st,r=ed; 
			while(1) {
				if(l==-1||r==len) break;
				if(s1[l] == s1[r]) l--,r++;
				else break;			
			}
			printf("%d\n",st-l+1);		
			continue;
		}
		top=0;
		str[top++] = '@';
		for(int i = 0; i<len; i++) {
			str[top++] = '#';
			str[top++] = s1[i];
		}
		str[top++] = '#';
		str[top] = '\0';
		manacher();
		ll ans = 0;
		for(int i = 2; i<top; i++) { 
			ans += p[i]/2;				
		}
		printf("%lld\n",ans);
	}
	return 0 ;
}
//@#a#a#a#
//@#a#a#