# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
205612 | 2020-02-29T10:05:10 Z | mihai50000 | 회문 (APIO14_palindrome) | C++17 | 51 ms | 30244 KB |
#include <bits/stdc++.h> using namespace std; #define int long long struct PalTree { struct Node { map <char, int> urm; int len; int cnt; int fail; }; int n = 2; int ans = 0; vector <Node> vec; PalTree(string s) : vec(s.size() + 2) { int m = s.size(); vec[0].len = vec[0].fail = -1; vec[1].len = vec[1].fail = 0; int last = 0; for(int i = 0; i < m; ++i) { char ch = s[i]; while(s[i - 1 - vec[last].len] != ch) last = vec[last].fail; if(vec[last].urm.count(ch)) { last = vec[last].urm[ch]; vec[last].cnt++; continue; } vec[n++].len = vec[last].len + 2; vec[n - 1].cnt = 1; vec[last].urm[ch] = n - 1; int fail = vec[last].fail; last = n - 1; while(fail != -1 && (ch != s[i - 1 - vec[fail].len] || !vec[fail].urm.count(ch))) { fail = vec[fail].fail; } if(fail < 1) fail = 1; vec[last].fail = fail; } for(int i = n - 1; i > 0; --i) vec[vec[i].fail].cnt += vec[i].cnt; for(int i = 1; i < n; ++i) { ans = max(ans, vec[i].len * vec[i].cnt); } } }; main() { string s; cin >> s; PalTree arb(s); cout << arb.ans << '\n'; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 256 KB | Output is correct |
2 | Correct | 5 ms | 256 KB | Output is correct |
3 | Incorrect | 5 ms | 376 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 1272 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 22 ms | 9720 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 51 ms | 30244 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |