QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#90121 | #5256. Insertions | whatever | WA | 4ms | 11996kb | C++14 | 3.3kb | 2023-03-22 13:29:55 | 2023-03-22 13:29:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
int n, m, k;
int f[N], nxt[N], mch[N];
int ans = -1, cnt, mn, mx;
char s[N], t[N], p[N];
void cnext(int n, char *s, int *nxt) {
for(int i = 2, j = 0; i <= n; i++) {
while(j && s[j + 1] != s[i]) j = nxt[j];
nxt[i] = j += s[j + 1] == s[i];
}
}
void match(int n, int m, char *s, char *t, int *mch) { // return occ
cnext(m, t, nxt);
for(int i = 1, j = 0; i <= n; i++) {
while(j && t[j + 1] != s[i]) j = nxt[j];
mch[i] = j += t[j + 1] == s[i];
}
}
namespace IN {
void solve() {
if(k >= m) return;
match(m, k, t, p, mch);
int occ = 0;
for(int i = 1; i <= m; i++) occ += mch[i] == k;
for(int i = 0; i <= n; i++) f[i] += occ;
}
}
namespace OUT {
int app[N], mchR[N];
char sR[N], pR[N];
vector<int> e[N];
vector<pair<int, int>> buc[N];
int dn, dfn[N], sz[N], c[N];
void dfs(int id) {
dfn[id] = ++dn, sz[id] = 1;
for(int it : e[id]) dfs(it), sz[id] += sz[it];
}
void add(int x, int v) {
while(x <= dn) c[x] += v, x += x & -x;
}
void add(int l, int r, int v) {
add(l, v), add(r + 1, -v);
}
int query(int x) {
int s = 0;
while(x) s += c[x], x -= x & -x;
return s;
}
void dfs2(int id) {
int _id = id + m, l = 0, r = 0;
if(_id <= k) l = dfn[k - _id], r = l + sz[k - _id] - 1;
if(_id <= k && app[_id]) add(l, r, 1);
for(auto _ : buc[id]) f[_.first] += query(dfn[_.second]);
for(int it : e[id]) dfs2(it);
if(_id <= k && app[_id]) add(l, r, -1);
}
void solve() {
if(k < m) return;
memcpy(sR, s, sizeof(s));
memcpy(pR, p, sizeof(p));
reverse(sR + 1, sR + n + 1);
reverse(pR + 1, pR + k + 1);
match(k, m, p, t, mch);
for(int i = 1; i <= k; i++) app[i] = mch[i] == m;
match(n, k, sR, pR, mchR);
for(int i = 1; i <= k; i++) e[nxt[i]].push_back(i);
dfs(0);
for(int i = 0; i < k; i++) e[i].clear();
match(n, k, s, p, mch);
for(int i = 1; i <= k; i++) e[nxt[i]].push_back(i);
for(int i = 0; i <= n; i++) buc[mch[i]].push_back({i, mchR[n - i]});
dfs2(0);
}
}
namespace CROSS {
int sz[N];
void solve() {
memset(sz, 0, sizeof(sz)); // add this line
match(k, m, p, t, mch);
int v = mch[k];
if(v == m) v = nxt[v];
while(v) sz[k - v]++, v = nxt[v];
match(n, k, s, p, mch);
for(int i = 1; i <= k; i++) sz[i] += sz[nxt[i]];
for(int i = 0, pre = 0; i <= n; i++) {
pre += mch[i] == k;
f[i] += sz[mch[i]] + pre;
}
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef ALEX_WEI
FILE* IN = freopen("1.in", "r", stdin);
FILE* OUT = freopen("1.out", "w", stdout);
#endif
cin >> s + 1 >> t + 1 >> p + 1;
n = strlen(s + 1);
m = strlen(t + 1);
k = strlen(p + 1);
IN::solve();
OUT::solve();
CROSS::solve();
reverse(s + 1, s + n + 1);
reverse(t + 1, t + m + 1);
reverse(p + 1, p + k + 1);
reverse(f, f + n + 1);
CROSS::solve();
reverse(f, f + n + 1);
for(int i = 0; i <= n; i++) {
if(f[i] > ans) ans = f[i], cnt = 1, mn = mx = i;
else if(f[i] == ans) cnt++, mx = i;
}
cout << ans << " " << cnt << " " << mn << " " << mx << "\n";
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
/*
g++ H.cpp -o H -std=c++14 -O2 -DALEX_WEI
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 9400kb
input:
rrddrrrdd ddrrd rrddrr
output:
2 2 6 7
result:
ok 4 number(s): "2 2 6 7"
Test #2:
score: -100
Wrong Answer
time: 4ms
memory: 11996kb
input:
z zzkkzzkk z
output:
6 2 0 1
result:
wrong answer 1st numbers differ - expected: '5', found: '6'