社区讨论
为何这样微微的改变会造成RE
学术版参与者 9已保存回复 13
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 13 条
- 当前快照
- 1 份
- 快照标识符
- @lo8qe14t
- 此快照首次捕获于
- 2023/10/27 22:51 2 年前
- 此快照最后确认于
- 2023/10/27 22:51 2 年前
下面有一份AC的manacher代码,
但是只要将
CPPint n;
char a[N], b[N];
int p[N];
改成
CPPint n, p[N];
char a[N], b[N];
就会RE成20分
求问这是为什么!
CPP#include <map>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
template <class T> inline void read(T &x){
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (f) x = -x;
}
template <class T> inline void print(T x){
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
const int N = 2e7 + 10;
int n;
char a[N], b[N];
int p[N];
inline void init(){
int k = 0;
b[k ++] = '$', b[k ++] = '#';
for(int i = 0; i < n; i ++) b[k ++] = a[i], b[k ++] = '#';
b[k ++] = '^';
n = k;
}
inline void manacher(){
int mr = 0, mid;
for(int i = 1; i < n; i ++){
if(i < mr) p[i] = min(p[mid * 2 - i], mr - i);
else p[i] = 1;
while(b[i - p[i]] == b[i + p[i]]) p[i] ++;
if(i + p[i] > mr){
mr = i + p[i];
mid = i;
}
}
}
signed main(){
scanf("%s", a);
n = strlen(a);
init(); manacher();
int res = 0;
for(int i = 0; i < n; i ++) res = max(res, p[i]);
print(res - 1);
return 0;
}
回复
共 13 条回复,欢迎继续交流。
正在加载回复...