社区讨论

为何这样微微的改变会造成RE

学术版参与者 9已保存回复 13

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
13 条
当前快照
1 份
快照标识符
@lo8qe14t
此快照首次捕获于
2023/10/27 22:51
2 年前
此快照最后确认于
2023/10/27 22:51
2 年前
查看原帖
下面有一份AC的manacher代码, 但是只要将
CPP
int n;
char a[N], b[N];
int p[N];
改成
CPP
int 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 条回复,欢迎继续交流。

正在加载回复...