为何这样微微的改变会造成RE
  • 板块学术版
  • 楼主Altwilio
  • 当前回复13
  • 已保存回复13
  • 发布时间2022/6/21 23:14
  • 上次更新2023/10/27 22:51:16
查看原帖
为何这样微微的改变会造成RE
574842
Altwilio楼主2022/6/21 23:14

下面有一份AC的manacher代码, 但是只要将

int n;
char a[N], b[N];
int p[N];

改成

int n, p[N];
char a[N], b[N];

就会RE成20分 求问这是为什么!

#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;
}
2022/6/21 23:14
加载中...