結果

問題 No.263 Common Palindromes Extra
ユーザー Suu0313Suu0313
提出日時 2023-03-14 00:00:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 3,490 bytes
コンパイル時間 2,811 ms
コンパイル使用メモリ 223,524 KB
実行使用メモリ 233,004 KB
最終ジャッジ日時 2023-10-18 11:25:38
合計ジャッジ時間 4,623 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 13 ms
4,444 KB
testcase_04 AC 54 ms
6,800 KB
testcase_05 AC 74 ms
6,420 KB
testcase_06 AC 7 ms
4,348 KB
testcase_07 AC 138 ms
62,780 KB
testcase_08 AC 153 ms
62,324 KB
testcase_09 AC 206 ms
119,432 KB
testcase_10 MLE -
testcase_11 AC 45 ms
5,892 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
    vector<int> cnt; // freq of this
    pair<int, int> idx; // one of the start pos

    Node() = default;
    Node(int n, int len): len(len), cnt(n, 0), 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:

  int n;
  vector<Node> nodes;
  vector<vector<T>> seq;
  // vector<vector<int>> ston;
  vector<int> suffix_max;


  MultiPalindromicTree(int n): n(n), seq(n), suffix_max(n){
    nodes.emplace_back(n, -1); // odd node
    nodes.emplace_back(n, 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;
      // ston[i].push_back(p);
      return;
    }

    // unique
    nodes[k].link[c] = suffix_max[i] = int(nodes.size());
    // ston[i].push_back(suffix_max[i]);
    int len = nodes[k].len + 2;
    nodes.emplace_back(n, 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<vector<int>> palindromes_frequency() const {
    int m = int(nodes.size());
    vector<vector<int>> freq(m, vector<int>(n));
    for(int i = m - 1; i >= 1; --i){
      for(int j = 0; j < n; ++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(2);
  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