有无C++大神解释一下?
  • 板块学术版
  • 楼主mori_
  • 当前回复13
  • 已保存回复13
  • 发布时间2023/8/31 13:51
  • 上次更新2023/11/3 00:12:43
查看原帖
有无C++大神解释一下?
339311
mori_楼主2023/8/31 13:51

这份manacher算法代码,为什么把对于s0s_0和s1s_1的赋值改在外面,char s[maxn] = {'A','M'};就会CE呢?

//
//  Created by mori on 2023/08/31 下午1:19 星期四
//
//  P3805 【模板】manacher 算法 on Luogu 
//  Coded with CLion
//  

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, x, y) for (int i = (x); i <= (y); ++i)

template <typename T>
void ckmax (T &_0, T _1) { if (_1 > _0) _0 = _1; }

const int maxn = 2e8;
char s[maxn << 1];
int ans, len = 1, p[maxn << 1];

signed main () {
    ios::sync_with_stdio(false);
    s[1] = 'M';
    while (cin >> s[++len]) s[++len] = 'M';
    s[0] = 'A';
    int r = 0, mid = 0;
    rep (i, 1, len) {
        p[i] = 1;
        if (r > i) p[i] = min(p[(mid << 1) - i], r - i + 1);
        while (s[i - p[i]] == s[i + p[i]]) ++p[i];
        if (i + p[i] - 1 > r) r = i + p[i] - 1, mid = i;
        ckmax(ans, p[i]);
    }
    printf("%d\n", ans - 1);
    return 0;
}
2023/8/31 13:51
加载中...