結果

問題 No.263 Common Palindromes Extra
ユーザー Suu0313Suu0313
提出日時 2023-03-14 00:08:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 196 ms / 2,000 ms
コード長 3,325 bytes
コンパイル時間 2,419 ms
コンパイル使用メモリ 218,380 KB
実行使用メモリ 139,288 KB
最終ジャッジ日時 2024-09-18 07:51:05
合計ジャッジ時間 3,902 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 11 ms
6,940 KB
testcase_04 AC 47 ms
6,940 KB
testcase_05 AC 68 ms
6,944 KB
testcase_06 AC 7 ms
6,944 KB
testcase_07 AC 88 ms
39,372 KB
testcase_08 AC 102 ms
39,340 KB
testcase_09 AC 114 ms
73,336 KB
testcase_10 AC 196 ms
139,288 KB
testcase_11 AC 41 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template<typename T = char>
struct MultiPalindromicTree{
private:
  struct Node{
    map<T, int> link;
    int link_rev = -1;
    int suffix_link = -1; // same suffix maximum pal
    int len; // palindrome length
    array<int, 2> cnt; // freq of this
    pair<int, int> idx; // one of the start pos

    Node() = default;
    Node(int len): len(len), cnt{}, idx(-1, -1) {}

    int succ(const T &c) const {
      auto it = link.find(c);
      if(it == link.end()) return -1;
      return it->second;
    }
  };

  // find longest P s.t. c + P + c is pal
  int find_next_pal(int p, int k) const {
    int pos = int(seq[p].size()) - 1;
    while(true){
      int i = pos - 1 - nodes[k].len;
      if(i >= 0 && seq[p][i] == seq[p][pos]) return k;
      k = nodes[k].suffix_link;
    }
  }

public:

  vector<Node> nodes;
  array<vector<T>, 2> seq = {};
  array<int, 2> suffix_max = {};


  MultiPalindromicTree(){
    nodes.emplace_back(-1); // odd node
    nodes.emplace_back(0); // even node
    nodes[1].suffix_link = 0;
  }

  void add(int i, const T &c){
    seq[i].push_back(c);
    int k = find_next_pal(i, suffix_max[i]);

    // c + P + c is already exists
    if(int p = nodes[k].succ(c); p != -1){
      ++nodes[p].cnt[i];
      suffix_max[i] = p;
      return;
    }

    // unique
    nodes[k].link[c] = suffix_max[i] = int(nodes.size());
    int len = nodes[k].len + 2;
    nodes.emplace_back(len);
    
    nodes.back().cnt[i] = 1;
    nodes.back().idx = {i, int(seq[i].size()) - len};
    nodes.back().link_rev = k;

    if(len == 1) nodes.back().suffix_link = 1;
    else nodes.back().suffix_link = 
      nodes[find_next_pal(i, nodes[k].suffix_link)].link[c];
  }

  template<class Iiter>
  void add(int i, Iiter first, Iiter last){
    for(; first != last; ++first) add(i, *first);
  }
  
  template<class Container>
  void add(int i, const Container &c){
    add(i, begin(c), end(c));
  }

  // idx of suffix palindromes of node k
  vector<int> suffix_palindromes(int k) const {
    vector<int> ret;
    for(; nodes[k].len > 0; k = nodes[k].suffix_link){
      ret.push_back(k);
    }
    return ret;
  }

  // idx of substring palindromes of node k
  vector<int> substr_palindroms(int k) const {
    vector<int> ret, seen(nodes.size());
    queue<int> qu;
    qu.push(k); seen[k] = 1;
    for(; !qu.empty(); qu.pop()){
      int v = qu.front();
      ret.push_back(v);
      for(int u : {nodes[v].suffix_link, nodes[v].link_rev}){
        if(!seen[u]) qu.push(u), seen[u] = 1;
      }
    }
    return ret;
  }

  // not count ""
  int count() const { return int(nodes.size()) - 2; }

  vector<array<int, 2>> palindromes_frequency() const {
    int m = int(nodes.size());
    vector<array<int, 2>> freq(m);
    for(int i = m - 1; i >= 1; --i){
      for(int j = 0; j < 2; ++j){
        freq[i][j] += nodes[i].cnt[j];
        freq[nodes[i].suffix_link][j] += freq[i][j];
      }
    }
    return freq;
  }

  const Node &operator[](int k) const { return nodes[k]; }
};


int main() {
  MultiPalindromicTree mpt;
  string s, t; cin >> s >> t;
  mpt.add(0, s);
  mpt.add(1, t);

  auto freq = mpt.palindromes_frequency();
  int64_t ans = 0;

  for(int i = 0; i < mpt.count(); ++i){
    ans += freq[i + 2][0] * 1ll * freq[i + 2][1];
  }

  cout << ans << "\n";
}
0