QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#194799 | #7512. Almost Prefix Concatenation | ucup-team484# | WA | 11ms | 17304kb | C++20 | 2.2kb | 2023-09-30 22:34:34 | 2023-09-30 22:34:35 |
Judging History
answer
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;
const int MAXN = 1000005;
LL mod = 998244353;
LL p = 31, pw[MAXN];
string s, t;
LL h_s[MAXN], h_t[MAXN];
array<array<LL, 3>, MAXN> suf;
LL bpow(LL b, LL x) {
LL ret = 1;
while(x) {
if(x & 1) {
ret = ret * b % mod;
}
b = b * b % mod;
x /= 2;
}
return ret;
}
LL inv(LL x) {
return bpow(x, mod - 2);
}
void compute_hash(string &s, LL h[]) {
h[0] = s[0] - 'a' + 1;
for(int i = 1; i < s.size(); ++i) {
h[i] = (h[i - 1] + pw[i] * (s[i] - 'a' + 1)) % mod;
}
}
LL hash_interval(LL h[], int l, int sz) {
LL ret = h[l + sz - 1] - h[l - 1];
ret = ret * inv(pw[l]) % mod;
return ret;
}
int get_next(int ls, int lt) {
if(ls == s.size() || lt == t.size()) {
return 0;
}
if(s[ls] != t[lt]) {
return 0;
}
int r = min(s.size() - ls + 1, t.size() - lt + 1), l = 0;
while(l + 1 < r) {
int m = (l + r) / 2;
if(hash_interval(h_s, ls, m) != hash_interval(h_t, lt, m)) {
r = m;
}
else l = m;
}
//cout << "bs: " << ls << " " << lt << " " << l << " " << r << endl;
return l;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> s >> t;
pw[0] = 1;
for(int i = 1; i < MAXN; ++i) {
pw[i] = pw[i - 1] * p % mod;
}
compute_hash(s, h_s);
compute_hash(t, h_t);
suf[s.size()] = {0, 0, 1};
for(int i = s.size() - 1; i >= 0; --i) {
int len = get_next(i, 0);
if(len < t.size() && i + len < s.size()) {
++len;
}
//cout << len << endl;
if(len < t.size() && i + len < s.size()) {
len = len + get_next(i + len, len);
}
auto [a,b,c] = suf[i + 1];
auto [a2, b2, c2] = suf[i + len + 1];
LL a3 = (a - a2 + mod) % mod, b3 = (b - b2 + mod) % mod, c3 = (c - c2 + mod) % mod;
suf[i] = {(a + a3 + 2*b3 + c3) % mod, (b + b3 + c3) % mod, (c3 + c) % mod};
//cout << i << " len: " << len << " " << suf[i][0] << " " << suf[i][1] << " " << suf[i][2] << endl;
}
cout << (suf[0][0] - suf[1][0] + mod) % mod << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 9ms
memory: 16132kb
input:
ababaab aba
output:
473
result:
ok 1 number(s): "473"
Test #2:
score: 0
Accepted
time: 4ms
memory: 16440kb
input:
ac ccpc
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: -100
Wrong Answer
time: 11ms
memory: 17304kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
948391364
result:
wrong answer 1st numbers differ - expected: '75038697', found: '948391364'