結果
問題 | No.263 Common Palindromes Extra |
ユーザー | MitI_7 |
提出日時 | 2016-03-17 21:24:08 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 191 ms / 2,000 ms |
コード長 | 1,864 bytes |
コンパイル時間 | 968 ms |
コンパイル使用メモリ | 79,908 KB |
実行使用メモリ | 146,796 KB |
最終ジャッジ日時 | 2023-08-20 00:35:32 |
合計ジャッジ時間 | 2,566 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 11 ms
9,612 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 21 ms
19,784 KB |
testcase_04 | AC | 85 ms
85,380 KB |
testcase_05 | AC | 112 ms
85,080 KB |
testcase_06 | AC | 11 ms
10,972 KB |
testcase_07 | AC | 112 ms
99,964 KB |
testcase_08 | AC | 130 ms
99,848 KB |
testcase_09 | AC | 135 ms
115,440 KB |
testcase_10 | AC | 191 ms
146,796 KB |
testcase_11 | AC | 75 ms
85,160 KB |
ソースコード
#include <iostream> #include <string> #include <vector> #include <map> #define ll long long #define FOR(i,a,b) for(int i= (a); i<((int)b); ++i) using namespace std; struct Node { map<char, ll> next; ll len = 0; ll sl = 0; }; class PalindromicTree { public: string str; vector<Node> tree; ll l_idx, ms_idx; PalindromicTree(string s) : str(s) { this->tree.resize(s.size() + 2); this->l_idx = 1; this->ms_idx = 1; this->tree[0].len = -1; } void addLetter(int pos) { char nc = this->str[pos]; ll A = ms_idx; while (true) { int p = pos - 1 - tree[A].len; if (p >= 0 && this->str[p] == nc) break; A = tree[A].sl; } if (this->tree[A].next[nc] != 0) { ms_idx = tree[A].next[nc]; return; } ms_idx = ++this->l_idx; Node &nn = tree[this->l_idx]; nn.len = tree[A].len + 2; tree[A].next[nc] = this->l_idx; if (nn.len == 1) { nn.sl = 1; return;} ll B = A; while (true) { B = tree[B].sl; int p = pos - 1 - tree[B].len; if (p >= 0 && this->str[p] == nc) break; } nn.sl = tree[B].next[nc]; } }; int main() { string s, t, u; cin >> s >> t; u = s + "<>" + t; vector<vector<ll>> dp(2, vector<ll>(u.size() + 2, 0)); PalindromicTree pt(u); FOR(i, 0, u.size()) { pt.addLetter(i); if (i < s.size()) { dp[0][pt.ms_idx]++; } if (i >= s.size() + 1) { dp[1][pt.ms_idx]++; } } ll ans = 0; for (int i = pt.l_idx; i >= 2; i--) { ans += dp[0][i] * dp[1][i]; dp[0][pt.tree[i].sl] += dp[0][i]; dp[1][pt.tree[i].sl] += dp[1][i]; } cout << ans << endl; return 0; }