結果

問題 No.263 Common Palindromes Extra
ユーザー _____TAB__________TAB_____
提出日時 2020-11-21 09:03:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 3,898 bytes
コンパイル時間 1,363 ms
コンパイル使用メモリ 90,468 KB
実行使用メモリ 197,132 KB
最終ジャッジ日時 2024-07-23 15:25:40
合計ジャッジ時間 2,743 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 12 ms
6,940 KB
testcase_04 AC 51 ms
12,416 KB
testcase_05 AC 45 ms
11,504 KB
testcase_06 AC 7 ms
6,944 KB
testcase_07 AC 139 ms
109,836 KB
testcase_08 AC 131 ms
111,124 KB
testcase_09 MLE -
testcase_10 AC 178 ms
185,976 KB
testcase_11 AC 42 ms
11,056 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <vector>
#include <array>
#include <iostream>

template<typename T, int alphabetSize, T min_element>
class PalindromicTree {

  struct Node {
    const int suffix_link;
    std::array<int,alphabetSize> ch;
    const int len;
    const int suffix_link_depth;// the number of palindromic suffixes
    int cnt;

    Node(int suffix_link, int len, int depth) :
      suffix_link(suffix_link), ch(), len(len), suffix_link_depth(depth), cnt(1) {
      std::fill(ch.begin(), ch.end(), -1);
    };

    void dump(){
      std::cerr << "cnt               : " << cnt << "\n";
      std::cerr << "suffix_link       : " << suffix_link << "\n";
      std::cerr << "suffix_link_depth : " << suffix_link_depth << "\n";
      for(int j = 0; j < alphabetSize; ++j){
        if(ch[j] >= 0){
          std::cout << std::string(1,'a'+j) << " " << ch[j] << std::endl;
        }
      }
      std::cerr << "\n";
    }
  };

public:

  std::vector<Node> nodes;
  std::vector<T> dat;
  int len;
  std::vector<int> A;

  PalindromicTree() : nodes({Node(-1,-1,0), Node(0,0,1)}), dat(), len(0), A() {}

  bool push_back(T c){
    dat.emplace_back(c);
    ++len;
    int parent_idx = A.empty() ? 0 : A.back();
    // std::cerr << parent_idx << " " << len-2-nodes[parent_idx].len << std::endl;
    while(len-2-nodes[parent_idx].len < 0 or dat[len-2-nodes[parent_idx].len] != c){
      parent_idx = nodes[parent_idx].suffix_link;
    }

    int v_idx = nodes[parent_idx].ch[c-min_element];

    if(v_idx != -1){
      ++nodes[v_idx].cnt;
      A.emplace_back(v_idx);
      return false;
    }

    int suffix_link = nodes[parent_idx].suffix_link;
    while(suffix_link >= 0 and (len-2-nodes[suffix_link].len < 0 or dat[len-2-nodes[suffix_link].len] != c)){
      suffix_link = nodes[suffix_link].suffix_link;
    }


    if(suffix_link >= 0 and len-2-nodes[suffix_link].len >= 0 and dat[len-2-nodes[suffix_link].len] == c){
      assert(nodes[suffix_link].ch[c-min_element] >= 0);
      suffix_link = nodes[suffix_link].ch[c-min_element];
    }

    if(suffix_link < 0) suffix_link = 1;
    
    v_idx = nodes.size();
    nodes[parent_idx].ch[c-min_element] = v_idx;
    nodes.emplace_back(suffix_link,nodes[parent_idx].len+2,nodes[parent_idx].suffix_link_depth+1);
    A.emplace_back(v_idx);
    
    return true;
  }

  size_t num_unique_palindrome() const noexcept {
    return nodes.size()-2;
  }
};

#include <iostream>
using namespace std;

void solve(){
  string s, t;
  cin >> s >> t;
  const int alphabet_size = 26;
  PalindromicTree<char,alphabet_size,'A'> S, T;

  for(auto c : s)
    S.push_back(c);
  for(auto c : t)
    T.push_back(c);
  
  for(int i = S.nodes.size()-1; i >= 0; --i){
    int sl = S.nodes[i].suffix_link;
    if(sl < 0) continue;
    S.nodes[sl].cnt += S.nodes[i].cnt;
  }
  for(int i = T.nodes.size()-1; i >= 0; --i){
    int sl = T.nodes[i].suffix_link;
    if(sl < 0) continue;
    T.nodes[sl].cnt += T.nodes[i].cnt;
  }
  
  string tmp;
  auto solve = [&](auto& solve, int vs, int vt) -> long long {
    long long ret = 0;
    if(S.nodes[vs].len > 0){
      long long cnt = (long long)(S.nodes[vs].cnt)*T.nodes[vt].cnt;
      ret += cnt;
    }
    for(int i = 0; i < alphabet_size; ++i){
      int us = S.nodes[vs].ch[i], ut = T.nodes[vt].ch[i];
      if(us < 0 or ut < 0)
        continue;
      tmp.push_back('A'+i);
      ret += solve(solve,us,ut);
      tmp.pop_back();
    }
    return ret;
  };

  long long ans = solve(solve,0,0) + solve(solve,1,1);
  cout << ans << endl;
}

void debug(){
  string s;
  cin >> s;
  const int alphabet_size = 26;
  PalindromicTree<char,alphabet_size,'a'> eerTree;
  for(auto c : s){
    eerTree.push_back(c);
  }
  for(size_t i = 0; i < eerTree.nodes.size(); ++i){
    cerr << "Node " << i << "\n";
    eerTree.nodes[i].dump();
  }
  cout << eerTree.num_unique_palindrome() << endl;
}

int main(){
  solve();
  // debug();
}
0