QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#164130 | #4275. Escape Sequences | wsyear | WA | 1ms | 5712kb | C++17 | 1.8kb | 2023-09-04 20:10:38 | 2023-09-04 20:10:38 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef dbg
#define D(...) fprintf(stderr, __VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ " = "), debug_helper::debug(__VA_ARGS__), D("\n")
#include "C:\Users\wsyear\Desktop\OI\templates\debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using namespace std;
const int N = 200010;
int n, m, a[N], b[N], fail[N], kmp[N];
char s[N], t[N];
bool check() {
// 判断 b 是否在 a 中出现
fail[1] = 0;
rep (i, 2, m) {
int j = fail[i - 1];
while (j && b[i] != b[j + 1]) j = fail[j];
fail[i] = j + (b[i] == b[j + 1]);
}
rep (i, 1, n) {
int j = kmp[i - 1];
while (j && a[i] != b[j + 1]) j = fail[j];
kmp[i] = j + (a[i] == b[j + 1]);
}
rep (i, 1, n) if (kmp[i] == m) return 1;
return 0;
}
int main() {
cin.tie(nullptr) -> ios::sync_with_stdio(false);
cin >> (s + 1) >> (t + 1);
n = strlen(s + 1), m = strlen(t + 1);
rep (i, 1, n) a[i] = s[i] - 'a';
rep (i, 1, m) b[i] = t[i] - 'a';
int ans = -1, cnt = 0;
while (m) {
if (check()) { ans = cnt; break; }
cnt++;
bool fa = 1, fb = 1;
rep (i, 1, m) {
if (i & 1) fa &= (b[i] == 0);
else fb &= (b[i] == 0);
}
if (m == 1) break;
if (fa) {
int mm = 0;
rep (i, 1, m) if (!(i & 1)) b[++mm] = b[m];
m = mm;
} else if (fb) {
int mm = 0;
rep (i, 1, m) if (i & 1) b[++mm] = b[m];
m = mm;
} else {
break;
}
}
cout << ans << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5660kb
input:
b ab
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5652kb
input:
ababa bab
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
a b
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5708kb
input:
abbb baa
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 5644kb
input:
abaabb abaab
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 5712kb
input:
aaab aaba
output:
1
result:
wrong answer 1st numbers differ - expected: '-1', found: '1'