結果
問題 | No.263 Common Palindromes Extra |
ユーザー | y_mazun |
提出日時 | 2015-08-31 23:30:23 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 3,702 bytes |
コンパイル時間 | 823 ms |
コンパイル使用メモリ | 67,724 KB |
実行使用メモリ | 100,180 KB |
最終ジャッジ日時 | 2023-08-20 00:34:30 |
合計ジャッジ時間 | 1,704 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
4,768 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 11 ms
7,228 KB |
testcase_04 | AC | 42 ms
22,660 KB |
testcase_05 | AC | 39 ms
22,472 KB |
testcase_06 | AC | 6 ms
5,288 KB |
testcase_07 | AC | 52 ms
42,140 KB |
testcase_08 | AC | 50 ms
41,928 KB |
testcase_09 | AC | 58 ms
61,580 KB |
testcase_10 | AC | 77 ms
100,180 KB |
testcase_11 | AC | 34 ms
22,260 KB |
ソースコード
#include <cstring> #include <cstdio> #include <iostream> #include <queue> #include <set> using namespace std; template<typename C, typename C::value_type low, typename C::value_type high, int bit = 32> class PalindromeTree{ const static int m = high - low + 1; const static int b = (m * bit + 31) / 32; typedef typename C::value_type T; struct node{ int next_[b]; int len; int sufflink; int next(int i){ const int bs = i * bit; const int be = i * bit + bit; const int ys = bs / 32; const int sc = min(bit, 32 - (bs % 32)); const int ye = be / 32; const int ec = bit - sc; int ret = 0; ret |= (next_[ys] >> (bs % 32)) & ((1ll << sc) - 1); if(ec != 0) ret |= (next_[ye] & ((1ll << ec) - 1)) << sc; return ret; } void next(int i, int v){ const int bs = i * bit; const int be = i * bit + bit; const int ys = bs / 32; const int sc = min(bit, 32 - (bs % 32)); const int ye = be / 32; const int ec = bit - sc; next_[ys] &= ~(((1ll << sc) - 1) << (bs % 32)); next_[ys] |= (v & ((1ll << sc) - 1)) << (bs % 32); if(ec != 0) next_[ye] &= ~((1ll << ec) - 1); if(ec != 0) next_[ye] |= (v >> sc) & ((1ll << ec) - 1); } }; const C s; int len; int num; void initTree(){ num = 2; suff = 2; tree[1].len = -1; tree[1].sufflink = 1; tree[2].len = 0; tree[2].sufflink = 1; } public: node *tree; int suff; bool addLetter(int pos){ int cur = suff; int curLen = 0; const int let = s[pos] - low; while(true){ curLen = tree[cur].len; if(pos - 1 - curLen >= 0 && s[pos - 1 - curLen] == s[pos]) break; cur = tree[cur].sufflink; } if(tree[cur].next(let)){ suff = tree[cur].next(let); return false; } num++; suff = num; tree[num].len = tree[cur].len + 2; tree[cur].next(let, num); if(tree[num].len == 1){ tree[num].sufflink = 2; return true; } while(true){ cur = tree[cur].sufflink; curLen = tree[cur].len; if(pos - 1 - curLen >= 0 && s[pos - 1 - curLen] == s[pos]){ tree[num].sufflink = tree[cur].next(let); break; } } return true; } PalindromeTree(const C &s) : s(s), len(s.size()), tree(new node[s.size() + 3]){ initTree(); } void build(){ for(int i = 0; i < len; i++){ addLetter(i); } } static long long countSamePalindrome(C &&s, C &&t, const C &sp){ long long ans = 0; const int ss = s.size(); const C sum = s + sp + t; s = t = ""; PalindromeTree tree(sum); vector<long long> scnt(sum.size() + 3); vector<long long> tcnt(sum.size() + 3); for(int i = 0; i < (int)sum.size(); i++){ tree.addLetter(i); int pos = tree.suff; const node &nd = tree.tree[pos]; if(i - nd.len + 1 < ss){ scnt[pos]++; }else if(i - nd.len + 1 >= (int)(ss + sp.size())){ tcnt[pos]++; } } for(int i = 0; i < 2; i++){ vector<long long> &v = i == 0 ? scnt : tcnt; for(int j = (int)v.size() - 1; j >= 3; j--){ const int suff = tree.tree[j].sufflink; if(suff >= 3){ v[suff] += v[j]; } } } for(int i = 3; i < (int)scnt.size(); i++){ ans += scnt[i] * tcnt[i]; } return ans; } }; typedef PalindromeTree<string, 'a', 'z'> SPalindromeTree; char buff[500000 + 10]; string getStr(){ scanf("%s", buff); return buff; } int main(){ string s = getStr(); string t = getStr(); typedef PalindromeTree<string, 'A' - 2, 'Z', 20> SPalindromeTree; printf("%lld\n", SPalindromeTree::countSamePalindrome(std::move(s), std::move(t), "@?")); return 0; }