結果
問題 | No.2606 Mirror Relay |
ユーザー |
![]() |
提出日時 | 2024-01-12 22:39:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 70 ms / 2,000 ms |
コード長 | 5,592 bytes |
コンパイル時間 | 2,306 ms |
コンパイル使用メモリ | 209,100 KB |
最終ジャッジ日時 | 2025-02-18 18:44:27 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 69 |
ソースコード
// https://math314.hateblo.jp/entry/2016/12/19/005919#include <bits/stdc++.h>using namespace std;struct PalindromicTree {//// private:struct node {map<char, int> link;int suffix_link;int len;int count;};vector<node> c;string s;int active_idx;node* create_node() {c.emplace_back();node* ret = &c.back();ret->count = 0;return ret;}// this->s の状態に依存する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;}bool debug_id2string_dfs(int v, int id, vector<char>& charas) {if (v == id) return true;for (auto kv : c[v].link) {if (debug_id2string_dfs(kv.second, id, charas)) {charas.push_back(kv.first);return true;}}return false;}public:PalindromicTree() {node* size_m1 = create_node(); // 長さ-1のノードを作成size_m1->suffix_link = 0; // -1 の親suffixは自分自身size_m1->len = -1;node* size_0 = create_node(); // 長さ0のノードを作成size_0->suffix_link = 0; // 親は長さ-1のノードsize_0->len = 0;active_idx = 0;}int get_active_idx() const {return active_idx;}node* get_node(int id) {return &c[id];}void add(char ch) {s.push_back(ch);// ch + [A] + ch が回文となるものを探すconst int a = find_prev_palindrome_idx(active_idx);//新しいノードへのリンクが発生するか試すconst auto inserted_result = c[a].link.insert(make_pair(ch, int(c.size())));active_idx = inserted_result.first->second; // insertの成否に関わらず、iteratorが指す先は新しい回文のindexif (!inserted_result.second) {c[active_idx].count++; // その回文が現れた回数が増加return; // 既にリンクが存在したので、新しいノードを作る必要がない}// 実際に新しいノードを作成node* nnode = create_node();nnode->count = 1;nnode->len = c[a].len + 2; // ch + [A] + ch だから、長さは len(A) + 2// suffix_linkの設定if (nnode->len == 1) {// この時だけsuffix_linkはsize 0に伸ばすnnode->suffix_link = 1;} else {// ch + [B] + ch が回文になるものを探す。ただし長さはaより小さいものconst int b = find_prev_palindrome_idx(c[a].suffix_link);nnode->suffix_link = c[b].link[ch];}}//各文字列が何回現れるか計算する// O(n)vector<int> build_frequency() {vector<int> frequency(c.size());//常に親ノードのid < 子ノードのidが成り立つので、idを大きい順から回せばよいfor (int i = int(c.size()) - 1; i > 0; i--) {frequency[i] += c[i].count;frequency[c[i].suffix_link] += frequency[i];}return frequency;}// debug用// idがどのような回文を表しているのかを返す// O(n)string debug_id2string(int id) {if (id == 0) {return "(-1)";} else if (id == 1) {return "(0)";}vector<char> charas;debug_id2string_dfs(0, id, charas);debug_id2string_dfs(1, id, charas);string ret(charas.begin(),charas.end());int start = int(charas.size()) - 1;if (c[id].len % 2 == 1) start--;for (int i = start; i >= 0; i--) ret.push_back(charas[i]);return ret;}void display_frequencies() {auto freq = build_frequency();printf("frequencies of each palindrome...\n");for (int i = 0; i < int(c.size()); i++) {const string palindrome = debug_id2string(i);printf(" %s : %d\n", palindrome.c_str(), freq[i]);}}};typedef long long ll;template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }#define all(x) (x).begin(),(x).end()#define fi first#define se second#define mp make_pair#define si(x) int(x.size())const int mod=998244353,MAX=300005,INF=1<<30;vector<int> G[MAX];ll ad[MAX],dp[MAX];int main() {std::ifstream in("text.txt");std::cin.rdbuf(in.rdbuf());cin.tie(0);ios::sync_with_stdio(false);string S;cin>>S;PalindromicTree pt;for (auto c : S) {pt.add(c); // 1文字ずつ登録していく//pt.display_frequencies();}auto fre=pt.build_frequency();for(int i=2;i<si(fre);i++){auto x=pt.get_node(i);//cout<<x->suffix_link<<" "<<x->len<<" "<<x->count<<endl;ad[i]+=(ll)(fre[i])*(x->len);G[x->suffix_link].push_back(i);}ll ans=0;for(int i=0;i<si(fre);i++){dp[i]+=ad[i];chmax(ans,dp[i]);for(int to:G[i]) chmax(dp[to],dp[i]);}cout<<ans<<endl;}