QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#280030 | #7780. Dark LaTeX vs. Light LaTeX | ucup-team1198# | WA | 0ms | 3880kb | C++14 | 3.0kb | 2023-12-09 13:27:18 | 2023-12-09 13:27:18 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
vector<int> get_pi(string s) {
vector<int> pi(s.size());
for (int i = 1; i < s.size(); ++i) {
int j = pi[i - 1];
while (j != -1 && s[i] != s[j])
j = j == 0 ? -1 : pi[j - 1];
pi[i] = j + 1;
}
return pi;
}
vector<int> get_z(string s) {
vector<int> z(s.size());
int j = 0;
for (int i = 1; i < s.size(); ++i) {
if (j + z[j] > i)
z[i] = min(j + z[j] - i, z[i - j]);
while (s[i + z[i]] == s[z[i]])
++z[i];
if (i + z[i] > j + z[j])
j = i;
}
return z;
}
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#endif
string s;
string t;
cin >> s >> t;
vector<vector<int>> s_pi(s.size());
for (int i = 0; i < s.size(); ++i) {
string cur = s.substr(i, s.size() - i) + '$' + s;
auto tmp = get_pi(cur);
vector<int> sum(tmp.size());
for (int j = 0; j < tmp.size(); ++j) {
if (tmp[j] == 0)
sum[j] = 0;
else
sum[j] = 1 + sum[tmp[j] - 1];
}
s_pi[i].resize(s.size());
for (int j = 0; j < s.size(); ++j)
s_pi[i][j] = tmp[s.size() - i + 1 + j];
}
vector<vector<int>> t_pi(t.size());
for (int i = 0; i < t.size(); ++i) {
string cur = t.substr(i, t.size() - i) + '$' + t;
auto tmp = get_pi(cur);
vector<int> sum(tmp.size());
for (int j = 0; j < tmp.size(); ++j) {
if (tmp[j] == 0)
sum[j] = 0;
else
sum[j] = 1 + sum[tmp[j] - 1];
}
t_pi[i].resize(t.size());
for (int j = 0; j < t.size(); ++j)
t_pi[i][j] = tmp[t.size() - i + 1 + j];
}
long long ans = 0;
for (int i = 0; i < s.size(); ++i) {
auto tmp = get_z(s.substr(i, s.size() - i) + '$' + t);
vector<int> cnts(s.size() + 1);
for (int j = 0; j < t.size(); ++j)
++cnts[tmp[s.size() - i + 1 + j]];
for (int j = int(s.size()) - 1; j >= 0; --j)
cnts[j] += cnts[j + 1];
for (int j = i; j < s.size(); ++j) {
ans += cnts[j - i + 1];
if (j + 1 < s.size() && i > 0)
ans += cnts[j - i + 1] * 1ll * s_pi[j + 1][i - 1];
}
}
for (int i = 0; i < t.size(); ++i) {
auto tmp = get_z(t.substr(i, t.size() - i) + '$' + s);
vector<int> cnts(t.size() + 1);
for (int j = 0; j < s.size(); ++j)
++cnts[tmp[t.size() - i + 1 + j]];
for (int j = int(t.size()) - 1; j >= 0; --j)
cnts[j] += cnts[j + 1];
for (int j = i; j < t.size(); ++j) {
if (j + 1 < t.size() && i > 0)
ans += cnts[j - i + 1] * 1ll * t_pi[j + 1][i - 1];
}
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3528kb
input:
abab ab
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
abab abaaab
output:
29
result:
ok 1 number(s): "29"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
abcd abcde
output:
10
result:
ok 1 number(s): "10"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
aaba ba
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3656kb
input:
babababaaabbaabababbbaabbbababbaaaaa aaaabbaababbab
output:
1488
result:
wrong answer 1st numbers differ - expected: '1161', found: '1488'