Strings in the Pocket（2019浙江省省赛）（马拉车

Strings in the Pocket（2019浙江省省赛）（马拉车

Strings in the Pocket（2019浙江省省赛）（马拉车-Manacher）

Time limit：1000 ms
Memory limit：65536 kB
judge：
ZOJ
vjudge

Description

BaoBao has just found two strings s = s 1 s 2 … s n s = s_1s_2dots s_n s=s1​s2​…sn​ and t = t 1 t 2 … t n t = t_1t_2dots t_n t=t1​t2​…tn​ in his left pocket, where s i s_i si​ indicates the i i i-th character in string s s s, and t i t_i ti​ indicates the i i i-th character in string t t t.

As BaoBao is bored, he decides to select a substring of s s s and reverse it. Formally speaking, he can select two integers l l l and r r r such that 1 ≤ l ≤ r ≤ n 1 le l le r le n 1≤l≤r≤n and change the string to s 1 s 2 … s l − 1 s r s r − 1 … s l + 1 s l s r + 1 … s n − 1 s n s_1s_2dots s_{l-1}s_rs_{r-1} dots s_{l+1}s_ls_{r+1}dots s_{n-1}s_n s1​s2​…sl−1​sr​sr−1​…sl+1​sl​sr+1​…sn−1​sn​.

In how many ways can BaoBao change s s s to t t t using the above operation exactly once? Let ( a , b ) (a, b) (a,b) be an operation which reverses the substring s a s a + 1 … s b s_as_{a+1} dots s_b sa​sa+1​…sb​, and ( c , d ) (c, d) (c,d) be an operation which reverses the substring s c s c + 1 … s d s_cs_{c+1} dots s_d sc​sc+1​…sd​. These two operations are considered different, if a ≠ c a ne c a​=c or b ≠ d b ne d b​=d.

Input

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

The first line contains a string s s s ( 1 ≤ ∣ s ∣ ≤ 2 × 1 0 6 1 le |s| le 2 times 10^6 1≤∣s∣≤2×106), while the second line contains another string t t t ( ∣ t ∣ = ∣ s ∣ |t| = |s| ∣t∣=∣s∣). Both strings are composed of lower-cased English letters.

It’s guaranteed that the sum of ∣ s ∣ |s| ∣s∣ of all test cases will not exceed 2 × 1 0 7 2 times 10^7 2×107.

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

题意

给你两个字符串 s s s 和 t t t ，你可以选择 s s s 的一个区间，然后区间内的元素左右翻转。此操作只能执行一次。问你有多少种操作可以使 s s s 变为 t t t 。

题解

假设 s s s 可以变为 t t t （废话）

那么还要分类讨论一下

1. 当 s s s 不等于 t t t 时，此时 s s s 和 t t t 一定有一段区间可以通过反转来变为 t t t 的对应区间。那么这一段区间就是一种答案。此外一次区间为基准向外扩展，因为如果此区间外左右两边的元素相同的话换与不换都不影响结果，所以包含他们就又是一种答案，以此类推，外面有几层相同的，答案就加几。
   
2. 当 s s s 等于 t t t 时，我们可以找到一个回文子串，然后反转这个区间，效果就相当于没反转，那么 s s s 和 t t t 还是相同的。所以问题就转化为了求 s s s 的回文子串的数目。
   由此想到了马拉车算法，因为p数组的意义就是以当前位置为中心的回文串的最大宽度。那么宽度就是回文串的半径，也就是可以组成的回文串的个数。但是由于马拉车算法往字符里塞了一些特殊字符，所以对p[i]/2求和即可。
   

代码

#include <iostream>
#include <cstring>
#define maxn 4000005
using namespace std;int p[maxn];
int T;
char str[maxn / 2], ttr[maxn / 2];
char ss[maxn];long long manacher() {int len = 0;ss[len++] = '$';ss[len++] = '#';int n = strlen(str);for (int i = 0; i < n; i++) {ss[len++] = str[i];ss[len++] = '#';}int mx = 0, id = 0;for (int i = 1; i < len; i++) {if (mx > i) p[i] = (p[2 * id - i] < (mx - i) ? p[2 * id - i] : (mx - i));else p[i] = 1;while (i - p[i] >= 0 && i + p[i] < len && ss[i - p[i]] == ss[i + p[i]]) p[i]++;if (i + p[i] > mx) {mx = i + p[i];id = i;}}long long ans = 0;for (int i = 2; i < len - 1; ++i) {if (ss[i] == '#') ans += p[i] / 2;else ans += (p[i] + 1) / 2;}return ans;
}int getno() {int ans = 1, len = strlen(str);int l = 0, r = len - 1;while (l < r && str[l] == ttr[l]) ++l;while (r > l && str[r] == ttr[r]) --r;for (int i = l, j = r; i <= r; ++i, --j) if (str[i] != ttr[j]) return 0;for (int i = l - 1, j = r + 1, le = len; i >= 0 && j < le && str[i] == ttr[j]; --i, ++j) ++ans;return ans;
}int main() {while (cin >> T) {for (int i = 0; i < T; ++i) {scanf("%s%s", str, ttr);if (strcmp(str, ttr) == 0) cout << manacher() << "n";else cout << getno() << "n";}}return 0;
}