結果
問題 | No.263 Common Palindromes Extra |
ユーザー | kriii |
提出日時 | 2019-08-24 21:42:51 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 242 ms / 2,000 ms |
コード長 | 1,727 bytes |
コンパイル時間 | 785 ms |
コンパイル使用メモリ | 72,820 KB |
実行使用メモリ | 150,248 KB |
最終ジャッジ日時 | 2024-04-22 14:04:09 |
合計ジャッジ時間 | 2,817 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 9 ms
5,376 KB |
testcase_04 | AC | 35 ms
6,044 KB |
testcase_05 | AC | 34 ms
5,376 KB |
testcase_06 | AC | 6 ms
5,376 KB |
testcase_07 | AC | 142 ms
99,680 KB |
testcase_08 | AC | 134 ms
99,680 KB |
testcase_09 | AC | 242 ms
150,248 KB |
testcase_10 | AC | 173 ms
150,132 KB |
testcase_11 | AC | 31 ms
5,376 KB |
ソースコード
#include <iostream> #include <vector> #include <string> using namespace std; struct eertree{ eertree(string &s){ push(s); } struct node{ int nxt[26] = { 0, }; int len = 0, suf = 0, occur = 0; }; vector<node> trie; int size, maxSuf; void push(string &str){ trie.clear(); trie.resize(3); size = 2; trie[1].len = -1, trie[1].suf = 1; trie[2].len = +0, trie[2].suf = 1; maxSuf = 2; for (int pos = 0; pos < str.length(); pos++) { int cur = maxSuf, len = 0, sym = str[pos] - 'A'; while (1){ len = trie[cur].len; if (pos - len - 1 >= 0 && str[pos - len - 1] == str[pos]) break; cur = trie[cur].suf; } if (trie[cur].nxt[sym]){ maxSuf = trie[cur].nxt[sym]; } else{ maxSuf = ++size; trie.push_back(node()); trie[size].len = trie[cur].len + 2; trie[cur].nxt[sym] = size; if (trie[size].len == 1){ trie[size].suf = 2; } else{ while (1){ cur = trie[cur].suf; len = trie[cur].len; if (pos - len - 1 >= 0 && str[pos - len - 1] == str[pos]){ trie[size].suf = trie[cur].nxt[sym]; break; } } } } trie[maxSuf].occur++; } for (int i = size; i >= 3; i--){ int suf = trie[i].suf; if (suf >= 3){ trie[suf].occur += trie[i].occur; } } } }; long long inter(eertree& a, eertree& b, int i, int j) { long long res = (long long)a.trie[i].occur * b.trie[j].occur; for (int sym = 0; sym < 26; sym++){ int nxtI = a.trie[i].nxt[sym]; int nxtJ = b.trie[j].nxt[sym]; if (nxtI && nxtJ){ res += inter(a, b, nxtI, nxtJ); } } return res; } int main() { string s, t; cin >> s >> t; eertree p(s), q(t); cout << inter(p, q, 1, 1) + inter(p, q, 2, 2); return 0; }