代码拉取完成,页面将自动刷新
#define y1 y__1
#include <algorithm>/*{{{*/
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
namespace RA {
int r(int p) { return 1ll * rand() * rand() % p; }
int r(int L, int R) { return r(R - L + 1) + L; }
} // namespace RA
/******************heading******************/
const int N = 1e5 + 5;
int n;
char s[N], rs[N];
int nex[N], l[N], p[N];
int h[N];
void get_next(char *s, int len) {
nex[1] = 0;
int i = 1, j = 0;
while (i <= len) {
if (j == 0 || s[i] == s[j])
++i, ++j, nex[i] = j;
else
j = nex[j];
}
}
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
memcpy(rs, s, sizeof(s));
reverse(rs + 1, rs + n + 1);
get_next(rs, n + 1);
int pos = 1, j = 1;
while (pos <= n) {
if (j == 0 || s[pos] == rs[j]) {
l[pos] = j;
++pos, ++j;
} else
j = nex[j];
if (j > n) j = nex[j];
}
FOR(i, 1, n)
if (l[i])
p[i] =
i - l[i] + 1; // l[i]表示前缀i可以匹配长度为l[i]的后缀;p[i]表示对应的匹配位置
FOR(i, 1, n) if (l[i - 1] > l[i]) l[i] = l[i - 1], p[i] = p[i - 1]; //前缀Max
int L = 0, R = 0;
FOR(i, 1, n) { // manacher
if (i < R) h[i] = min(R - i, h[L + R - i]);
while (
1 <= i - h[i] - 1 && i + h[i] + 1 <= n && s[i - h[i] - 1] == s[i + h[i] + 1])
++h[i];
if (i + h[i] > R) L = i - h[i], R = i + h[i];
}
int ans = 0;
FOR(i, 1, n)
ans = max(ans, h[i] * 2 + 1 + 2 * min(l[i - h[i] - 1], n - i - h[i])); //算答案
FOR(i, 1, n) { //输出方案
if (ans == h[i] * 2 + 1 + 2 * min(l[i - h[i] - 1], n - i - h[i])) {
int x1 = p[i - h[i] - 1], y1 = min(l[i - h[i] - 1], n - i - h[i]);
int x2 = i - h[i], y2 = h[i] * 2 + 1;
int x3 = n - y1 + 1, y3 = y1;
int k = !!y1 + !!y2 + !!y3;
printf("%d\n", k);
if (y1) printf("%d %d\n", x1, y1);
if (y2) printf("%d %d\n", x2, y2);
if (y3) printf("%d %d\n", x3, y3);
return 0;
}
}
return 0;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。