結果
問題 | No.263 Common Palindromes Extra |
ユーザー |
|
提出日時 | 2023-04-28 13:11:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 146 ms / 2,000 ms |
コード長 | 2,512 bytes |
コンパイル時間 | 3,322 ms |
コンパイル使用メモリ | 258,036 KB |
実行使用メモリ | 121,532 KB |
最終ジャッジ日時 | 2024-11-17 13:49:28 |
合計ジャッジ時間 | 4,037 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct Node {map<char, int> link;int suffix_link;int len;int count;};struct PalindromicTree {vector<Node> c;string s;int active_idx;Node& create_node() {c.emplace_back();Node& ret = c.back();ret.count = 0;return ret;}int find_prev_palindrome_idx(int node_id) {const int pos = int(s.size() - 1);while (true) {const int opposite_side_idx = pos - 1 - c[node_id].len;if (opposite_side_idx >= 0 && s[opposite_side_idx] == s.back()) {break;}node_id = c[node_id].suffix_link;}return node_id;}PalindromicTree() {Node& size_m1 = create_node();size_m1.suffix_link = 0;size_m1.len = -1;Node& size_0 = create_node();size_0.suffix_link = 0;size_0.len = 0;active_idx = 0;}void add(char ch) {s.push_back(ch);const int a = find_prev_palindrome_idx(active_idx);auto result = (c[a].link.count(ch) > 0);if (result) {active_idx = c[a].link[ch];c[active_idx].count++;return;} else {c[a].link[ch] = c.size();active_idx = c.size();}Node& new_node = create_node();new_node.count = 1;new_node.len = c[a].len + 2;if (new_node.len == 1) {new_node.suffix_link = 1;} else {const int b = find_prev_palindrome_idx(c[a].suffix_link);new_node.suffix_link = c[b].link[ch];}}vector<int> build_frequency() {vector<int> freq(c.size());for (int i = (int) c.size() - 1; i > 0; i--) {freq[i] += c[i].count;freq[c[i].suffix_link] += freq[i];}return freq;}};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);string s, t;cin >> s >> t;int n = s.size(), m = t.size();string st = s + ",." + t;PalindromicTree pt;for (int i = 0; i < n; i++) {pt.add(st[i]);}auto freq = pt.build_frequency();for (int i = n; i < n + m + 2; i++) {pt.add(st[i]);}auto freq2 = pt.build_frequency();long long ans = 0;for (int i = 2; i < (int) freq.size(); i++) {ans += (long long) (freq2[i] - freq[i]) * freq[i];}cout << ans << '\n';}