- ABCBAC
1
- @ 2026-7-22 11:47:22
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
template<int B, int mod>
struct Hash {
// int B = 133331, mod = 1e9 + 7;
vector<ll> h, p;
Hash(string s) {
int n = s.size();
h.resize(n); p.assign(n, 1);
h[0] = s[0];
for (int i = 1; i < n; i++) {
h[i] = h[i-1] * B + s[i];
h[i]%=mod;
p[i] = p[i - 1] * B % mod;
}
}
ll get(int l, int r) {
if (l > r) return 0ll;
ll H = h[r] - h[l - 1] * p[(r - l + 1)];
return (H % mod + mod) % mod;
}
};
void solve() {
int n;
cin >> n;
string s;
cin >> s;
auto t = s;
reverse(t.begin(), t.end());
s = ' ' + s + t;
const int B = 13331, mod = 1e9 + 7;
Hash<B, mod> hash(s);
for (int i = 0; i <= n; i++) {
auto h1 = hash.get(3 * n + 1 - i, 4 * n - i);
auto h2 = (hash.get(1, i) * hash.p[(n - i)] + hash.get(n + i + 1, 2 * n)) % mod;
if (h1 == h2) {
cout << s.substr(1, i) + s.substr(n + i + 1, n - i) << '\n';
cout << i << '\n';
return;
}
}
cout << "-1\n";
}
signed main() {
// long double p = 1e18;
// cout << powl(1 - 1 / p, 2e6) << '\n';
int t = 1;
while (t--) solve();
return 0;
}
/*
g++ -std=c++20 1.cpp -o 1 && 1 < in.txt > out.txt
*/
1 条评论
-
杨志杰 黄金 Lv.初识 @ 2026-7-22 11:51:17#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> template<int B, int mod> struct Hash { // int B = 133331, mod = 1e9 + 7; vector<ll> h, p; Hash(string s) { int n = s.size(); h.resize(n); p.assign(n, 1); h[0] = s[0]; for (int i = 1; i < n; i++) { h[i] = h[i-1] * B + s[i]; h[i]%=mod; p[i] = p[i - 1] * B % mod; } } ll get(int l, int r) { if (l > r) return 0ll; ll H = h[r] - h[l - 1] * p[(r - l + 1)]; return (H % mod + mod) % mod; } }; void solve() { int n; cin >> n; string s; cin >> s; auto t = s; reverse(t.begin(), t.end()); s = ' ' + s + t; const int B = 13331, mod = 1e9 + 7; Hash<B, mod> hash(s); for (int i = 0; i <= n; i++) { auto h1 = hash.get(3 * n + 1 - i, 4 * n - i); auto h2 = (hash.get(1, i) * hash.p[(n - i)] + hash.get(n + i + 1, 2 * n)) % mod; if (h1 == h2) { cout << s.substr(1, i) + s.substr(n + i + 1, n - i) << '\n'; cout << i << '\n'; return; } } cout << "-1\n"; } signed main() { // long double p = 1e18; // cout << powl(1 - 1 / p, 2e6) << '\n'; int t = 1; while (t--) solve(); return 0; } /* g++ -std=c++20 1.cpp -o 1 && 1 < in.txt > out.txt */ ``
- 1
信息
- ID
- 499
- 时间
- ms
- 内存
- MiB
- 难度
- 6
- 标签
- 递交数
- 58
- 已通过
- 17
- 上传者