RT,这份代码编译过后运行会直接得到 SIGSEGV 也就是 Segmentation fault 的结果。
// author : black_trees
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;
using i64 = long long;
const int si = 2e5 + 10;
class StringWithDoubleHash {
private:
string s; i64 len;
i64 h[2][si], power[2][si];
const i64 base = 131;
const i64 m[2] = {998244853ll, 1000000009ll};
public:
int Size() { return len; }
i64 Index(char ch) { return (i64)(ch - 'a'); }
void Init(string t) {
s = ' ' + t, len = (int)t.size();
power[0][0] = power[1][0] = 1ll;
for(int _ = 0; _ <= 1; ++_) {
for(int i = 1; i <= len; ++i) {
power[_][i] = power[_][i - 1] * base % m[_];
}
}
h[0][0] = h[1][0] = 0ll;
for(int _ = 0; _ <= 1; ++_) {
for(int i = 1; i <= len; ++i) {
h[_][i] = (h[_][i - 1] * base) % m[_] + Index(s[i]) % m[_];
}
}
}
i64 Query(int _, int l, int r) {
return (h[_][r] - (h[_][l - 1] * power[_][r - l + 1] % m[_]) + m[_]) % m[_];
}
bool Equal(int l1, int r1, int l2, int r2) {
bool f = true;
for(int _ = 0; _ <= 1; ++_) {
f &= (Query(_, l1, r1) == Query(_, l2, r2));
}
return f;
}
};
using str = StringWithDoubleHash;
bool Equal(str a, str b, int l, int r) {
if(a.Size() != b.Size()) return false;
bool f = true;
for(int i = 0; i <= 1; ++i)
f &= (a.Query(i, l, r) == b.Query(i, l, r));
return f;
}
int Radius(str s, int l, int r, int c) {
while(l < r) {
int mid = (l + r + 1) >> 1;
if(c - mid + 1 >= 1 && c + mid - 1 <= s.Size()
&& s.Equal(c - mid + 1, c, c, c + mid - 1))
l = mid;
else r = mid - 1;
}
return l;
}
int Radius_ignore(str s, int l, int r, int c, int Ra) {
while(l < r) {
int mid = (l + r + 1) >> 1;
if(c - mid + 1 >= 1 && c + mid - 1 <= s.Size()
&& s.Equal(c - mid + 1, c - Ra - 1, c + Ra + 1, c + mid - 1))
l = mid;
else r = mid - 1;
}
return l;
}
str s;
int Rad[si];
int delta[si][27];
int pre[si], suf[si], cnt[si];
void fix(int a[], int l, int r, int v) {
a[r] += v, a[l - 1] -= v;
}
void redo(int a[], int n) {
for(int i = 1; i <= n; ++i)
a[i] = a[i] + a[i + 1];
}
int main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit | cin.badbit);
string tmp; cin >> tmp;
string t = "#";
for(int i = 0; i < (int)tmp.size(); ++i)
t += tmp[i], t += '#';
s.Init(t), t = ' ' + t;
// cout << t << endl;
int n = s.Size(), sum = 0;
for(int i = 1; i <= n; ++i) {
Rad[i] = Radius(s, 1, n, i);
sum = sum + (Rad[i] / 2);
int L = i - Rad[i] + 1, R = i + Rad[i] - 1;
// loosen
if(L - 1 >= 1 && R + 1 <= n) {
char ch1 = t[L - 1], ch2 = t[R + 1];
int Rr = Radius_ignore(s, Rad[i], n, i, Rad[i]);
delta[L - 1][(int)(ch2 - 'a' + 1)] += Rr - Rad[i];
delta[R + 1][(int)(ch1 - 'a' + 1)] += Rr - Rad[i];
}
// lessen
fix(pre, L, i, L), fix(suf, i, R, R), fix(cnt, L, R, 1);
}
redo(pre, n), redo(suf, n), redo(cnt, n);
// for(int i = 1; i <= n; ++i) cout << Rad[i] << endl;
int ans = -1;
for(int i = 1; i <= n; ++i) {
if(t[i] == '#') continue;
for(char ch = 'a'; ch <= 'z'; ++ch) {
int add = delta[i][(int)(ch - 'a' + 1)];
int sub = pre[i] + suf[i] - (i * cnt[i]);
ans = max(ans, sum + (add - sub) / 2);
}
}
cout << ans << endl;
return 0;
}
// ()()()(?
经过 gdb 调试得到了以下信息:
Reading symbols from T4...
(gdb) r
Starting program: C:\Users\Administrator\OneDrive\Workspace\Code\Mockcontests\20230201C\T4.exe
[New Thread 8836.0x23e0]
[New Thread 8836.0x2cd4]
[New Thread 8836.0x2a90]
Thread 1 received signal SIGSEGV, Segmentation fault.
0x00007ff7b6ec29c6 in ___chkstk_ms ()
(gdb)
经过各种搜索找到了这个函数的源码注释:
/* ___chkstk_ms is a *special* function call, which uses %rax as the argument.We avoid clobbering any registers. Unlike ___chkstk, it just probes the stack and does no stack allocation. */
功能大致是在分配一个新的栈之后进行一些检查
猜测是申请栈空间的时候触发了什么错误,但是具体并不清楚,网上也没有类似的原因。
而且因为是运行就 RE 了,我猜测大概率问题出在 class StringWithDoubleHash 当中,但是并没有看出来问题。
各种询问无果,所以发个帖看看有没有大佬能看出来/kk,万分感谢