QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#80034 | #5440. P-P-Palindrome | APJifengc | WA | 2ms | 14000kb | C++20 | 2.4kb | 2023-02-21 20:08:58 | 2023-02-21 20:09:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int n;
char s[MAXN];
const int P1 = 993244853, BASE1 = 131;
const int P2 = 1000000009, BASE2 = 13331;
int B1[MAXN], B2[MAXN];
struct Hash {
long long a1, a2;
bool operator==(const Hash &b) const {
return a1 == b.a1 && a2 == b.a2;
}
bool operator<(const Hash &b) const {
return a1 == b.a1 ? a2 < b.a2 : a1 < b.a1;
}
Hash operator+(const int b) const {
return { (a1 * BASE1 + b) % P1, (a2 * BASE2 + b) % P2 };
}
Hash operator<<(const int b) const {
return { a1 * B1[b] % P1, a2 * B2[b] % P2 };
}
Hash operator-(const Hash &b) const {
return { (a1 - b.a1 + P1) % P1, (a2 - b.a2 + P2) % P2 };
}
} h[MAXN];
Hash split(int l, int r) {
return h[r] - (h[l - 1] << (r - l + 1));
}
map<Hash, int> cnt;
struct PalindromeAutomaton {
int t[MAXN][26], len[MAXN], fail[MAXN];
int lst, tot;
PalindromeAutomaton() {
len[1] = -1, fail[0] = 1;
lst = tot = 1;
}
void insert(int c, int i) {
int p = lst;
while (s[i - len[p] - 1] != s[i]) p = fail[p];
if (!t[p][c]) {
++tot;
int q = fail[p];
while (s[i - len[q] - 1] != s[i]) q = fail[q];
fail[tot] = t[q][c];
len[tot] = len[p] + 2;
t[p][c] = tot;
int diff = len[tot] - len[fail[tot]];
int l = (len[tot] % diff == 0 ? diff : len[tot]);
// printf("l = %d\n", l);
cnt[split(i - l + 1, i)] = max(cnt[split(i - l + 1, i)], len[tot] / l);
}
lst = t[p][c];
}
} pam;
int main() {
scanf("%d", &n);
B1[0] = B2[0] = 1;
for (int i = 1; i <= n; i++) {
B1[i] = 1ll * B1[i - 1] * BASE1 % P1;
B2[i] = 1ll * B2[i - 1] * BASE2 % P2;
}
for (int i = 1; i <= n; i++) {
scanf("%s", s + 1);
int m = strlen(s + 1);
for (int j = 1; j <= m; j++) {
h[j] = h[j - 1] + (s[j] - 'a' + 1);
}
pam.lst = 0;
for (int j = 1; j <= m; j++) {
pam.insert(s[j] - 'a', j);
}
}
long long ans = 0;
for (auto p : cnt) {
// printf("(%lld, %lld): %d\n", p.first.a1, p.first.a2, p.second);
ans += 1ll * p.second * p.second;
}
printf("%lld\n", ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 13800kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 1ms
memory: 13788kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 0ms
memory: 14000kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 13884kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1286
result:
wrong answer 1st numbers differ - expected: '1282', found: '1286'