题目描述
难度分:2800
输入长度≤105的字符串s，只包含小写英文字母。
有一个奇回文串t，设t=pre+mid+suf，其中mid的长度是奇数，pre和suf的长度相等（可以为0）。
已知s=A+pre+B+mid+C+suf（A、B、C可以为空），求t的最大长度。
输出格式：
首先输出t有几段。如果pre的长度为0，则输出1，否则输出3。
然后输出每段首字母在s中的下标（从1开始），以及这一段的长度。多解输出任意解。
输入样例1
abacaba
输出样例1
1
1 7
输入样例2
axbya
输出样例2
3
1 1
2 1
5 1
输入样例3
xabyczba
输出样例3
3
2 2
4 1
7 2
算法
kmp算法+字符串哈希+二分
判断回文可以用字符串哈希O(1)做到，因此我们可以先对s串做一个字符串哈希，然后分以下两种情况考虑。
1. pre和suf都为空
遍历i∈[1,n]，维护此时的最长回文串pre+mid+suf长度maxlen。如果以s[i]为mid的中心，那么我们是可以二分出这个奇数长度回文串的最长半径的，因为存在单调性：
- 如果子串[i,i+len−1]和[i−len+1,i]的反转是相等的（可以用字符串哈希O(1)判断出来），那么子串[i−len+1,i+len−1]就是个回文串，这时候可以尝试更大的半径看看这个回文串还能不能更长。
- 如果子串[i,i+len−1]和[i−len+1,i]的反转是不相等的，那么更长的半径肯定也不会让子串[i,i+len−1]和[i−len+1,i]的反转相等，从而让子串[i−len+1,i+len−1]是回文串。
通过这种方式就可以得到“pre=suf=空串”的情况下，t的最大长度。
2. pre和suf都不为空
注意到suf是s串的一个后缀，这时候又发现单调性，对于s的两个后缀s[j…n]和s[i…n]，如果它们的反转串在s串中都有出现，那么较短串出现的位置一定不会晚于较长串出现的位置（最早出现位置），因为较长串是包含较短串的，较长串的出现必然伴随着一次较短串的出现，不可能较长串出现了，较短串在它后面出现。因此这里又可以二分这个最长suf的长度了，对于以s[i]为中心的mid串，如果它的范围是[l,r]：
- 当s[i…n]的反转串出现在l左边时（即这个反转串的右端点在l的左边，不会碰到），n−i+1这个长度的suf是没有问题的，可以记录一下答案然后往右搜索看更长的suf行不行。
- 否则说明s[i…n]的反转串的最早出现位置已经越过l了，再长的suf肯定也不会早于这个串出现，所以往左搜索更短串的长度。
这样一来就可以得到pre和suf不为空时的最大t串长度，只需要维护这个最大的长度，以及pre、mid、suf三段的起始位置和长度即可。
此时只剩下一个关键问题“如何确定s的每个后缀的反转串在s中出现的最早位置？”，可以将整个s反转得到一个字符串rs，然后问题就转化为“求rs的每个前缀在s中出现的最早位置”，这个经典问题可以用kmp算法在线性时间复杂度O(n)下预处理出来，也可以用后缀自动机做这个预处理。
复杂度分析
时间复杂度
预处理的时间复杂度是线性的，为O(n)；接下来两种情况都要遍历i∈[1,n]，而对于每个给定的i，都需要进行二分，时间复杂度为O(log2n)，这个过程的总时间复杂度为O(nlog2n)。整个算法的时间复杂度即为O(nlog2n)。
空间复杂度
字符串哈希的空间复杂度为O(n)；t串的规模和s串相同，空间复杂度为O(n)；kmp预处理的空间消耗也是O(n)的。因此，整个算法的额外空间复杂度为O(n)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;
class StringHash {
public:
explicit StringHash(string& s, int base1=131, int base2=13131) {
n = s.size();
p1.resize(n + 1);
h1.resize(n + 1);
rev_h1.resize(n + 1);
p2.resize(n + 1);
h2.resize(n + 1);
rev_h2.resize(n + 1);
p1[0] = p2[0] = 1;
for(int i = 1; i <= n; i++){
h1[i] = (h1[i - 1] * base1 % MOD + s[i - 1]) % MOD;
p1[i] = p1[i - 1] * base1 % MOD;
h2[i] = (h2[i - 1] * base2 % MOD + s[i - 1]) % MOD;
p2[i] = p2[i - 1] * base2 % MOD;
}
for(int i = n; i >= 1; i--) {
rev_h1[i] = (rev_h1[i + 1] * base1 % MOD + s[i - 1]) % MOD;
rev_h2[i] = (rev_h2[i + 1] * base2 % MOD + s[i - 1]) % MOD;
}
}
bool is_palindrome(int left, int right){
if(left > right) return true; // 空串
pair<LL, LL> u1 = shash(left, right);
pair<LL, LL> u2 = shash(left, right, true);
return u1.first == u2.first && u1.second == u2.second;
}
pair<LL, LL> shash(int left, int right, bool is_rev=false) {
++left, ++right;
LL u1 = is_rev? (rev_h1[left] - rev_h1[right + 1]*p1[right - left + 1]%MOD + MOD) % MOD: (h1[right] - h1[left - 1]*p1[right - left + 1]%MOD + MOD) % MOD;
LL u2 = is_rev? (rev_h2[left] - rev_h2[right + 1]*p2[right - left + 1]%MOD + MOD) % MOD: (h2[right] - h2[left - 1]*p2[right - left + 1]%MOD + MOD) % MOD;
return {u1, u2};
}
private:
int base1, base2, n;
vector<LL> h1, rev_h1, p1, h2, rev_h2, p2;
};
vector<int> preprocess(string& s, string& t) {
int n = t.size(), m = s.size();
vector<int> t_list(n);
for(int i = 0; i < n; ++i) {
t_list[i] = t[i] - 'a';
}
vector<int> next(n + 1, -1);
int kmp_k = -1;
for(int j = 0; j < n; ) {
if(kmp_k == -1 || t_list[j] == t_list[kmp_k]) {
++j;
++kmp_k;
next[j] = kmp_k;
}else {
kmp_k = next[kmp_k];
}
}
vector<vector<int>> delta(n, vector<int>(26, 0));
for(int k = 0; k < n; k++) {
for(int c = 0; c < 26; c++) {
if(k == 0) {
delta[k][c] = (c == t_list[0])? 1 : 0;
}else {
delta[k][c] = (c == t_list[k])? k + 1: delta[next[k]][c];
}
}
}
vector<int> ans(n + 1, -1);
int current_state = 0;
for(int i = 0; i < m; ++i) {
int c = s[i] - 'a';
current_state = delta[current_state][c];
if(current_state > 0 && ans[current_state] == -1) {
ans[current_state] = i - current_state + 1;
}
}
return ans;
}
int main() {
string s;
cin >> s;
string t = "" + s;
reverse(t.begin(), t.end());
vector<int> pos = preprocess(s, t);
StringHash sh(s);
int n = s.size();
vector<int> mid_maxlen(n);
for(int i = 0; i < n; i++) {
int l = 1, r = min(i + 1, n - i);
while(l < r) {
int m = l + r + 1 >> 1;
auto lhash = sh.shash(i - m + 1, i, true);
auto rhash = sh.shash(i, i + m - 1);
if(lhash.first == rhash.first && lhash.second == rhash.second) {
l = m;
}else {
r = m - 1;
}
}
// 以s[i]为中心的最长奇回文串为[i-r+1,i+r-1]
mid_maxlen[i] = r*2 - 1;
}
int maxlen = 1;
vector<int> mid = {1, 1}, pre = {0, 0}, suf = {0, 0};
for(int i = 0; i < n; i++) {
int half = mid_maxlen[i]>>1;
int l = i - half, r = i + half;
// [left,right]是以i为中心的奇数长度回文串
if(2*half + 1 > maxlen) {
// pre和suf都是空的情况
maxlen = 2*half + 1;
mid[0] = l + 1, mid[1] = maxlen;
pre[0] = pre[1] = suf[0] = suf[1] = 0;
}
}
for(int i = 0; i < n; i++) {
int half = mid_maxlen[i]>>1;
int l = i - half, r = i + half;
// 考虑pre和suf都非空的情况，找一个最长后缀[j,n-1]，它的反转在l的左边也完整出现
int low = 1, high = n - 1 - r, len = 0;
while(low <= high) {
int middle = low + high >> 1;
if(pos[middle] != -1 && pos[middle] + middle - 1 < l) {
len = middle;
low = middle + 1;
}else {
high = middle - 1;
}
}
if(len*2 + mid_maxlen[i] > maxlen) {
maxlen = len*2 + mid_maxlen[i];
mid[0] = l + 1, mid[1] = mid_maxlen[i];
pre[0] = pos[len] + 1, pre[1] = len;
suf[0] = n - len + 1, suf[1] = len;
}
}
if(pre[0] == 0) {
printf("1\n%d %d\n", mid[0], mid[1]);
}else {
printf("3\n%d %d\n%d %d\n%d %d\n", pre[0], pre[1], mid[0], mid[1], suf[0], suf[1]);
}
return 0;
}
