1 Star 4 Fork 0

Sshwy/code

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
克隆/下载
30e.cpp 2.37 KB
一键复制 编辑 原始数据 按行查看 历史
Sshwy 提交于 4年前 . format files
#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;
}
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/sshwy/code.git
git@gitee.com:sshwy/code.git
sshwy
code
code
master

搜索帮助