結果

問題 No.263 Common Palindromes Extra
ユーザー _____TAB__________TAB_____
提出日時 2020-11-21 09:14:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 200 ms / 2,000 ms
コード長 3,700 bytes
コンパイル時間 1,106 ms
コンパイル使用メモリ 83,696 KB
実行使用メモリ 190,772 KB
最終ジャッジ日時 2024-07-23 15:26:06
合計ジャッジ時間 2,281 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 11 ms
6,944 KB
testcase_04 AC 50 ms
12,144 KB
testcase_05 AC 44 ms
11,492 KB
testcase_06 AC 7 ms
6,940 KB
testcase_07 AC 122 ms
106,976 KB
testcase_08 AC 120 ms
106,836 KB
testcase_09 AC 200 ms
190,772 KB
testcase_10 AC 136 ms
181,152 KB
testcase_11 AC 43 ms
11,052 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;
    int cnt;

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

    // void dump(){
    //   std::cerr << "cnt               : " << cnt << "\n";
    //   std::cerr << "suffix_link       : " << suffix_link << "\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), Node(0,0)}), 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);
    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;
  }
  
  auto solve = [&](auto&& solve, const int& vs, const 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;
      ret += solve(solve,us,ut);
    }
    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