結果

問題 No.263 Common Palindromes Extra
コンテスト
ユーザー miscalc
提出日時 2025-10-24 04:51:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 125 ms / 2,000 ms
コード長 2,568 bytes
コンパイル時間 3,003 ms
コンパイル使用メモリ 288,484 KB
実行使用メモリ 150,384 KB
最終ジャッジ日時 2025-10-24 04:51:22
合計ジャッジ時間 4,532 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using ll = long long;
using pll = pair<ll, ll>;
#define vc vector
using vl = vc<ll>;

#define ov(a, b, c, name, ...) name
#define rep2(i, l, r) for(ll i = (l); i < ll(r); i++)
#define rep1(i, n) rep2(i, 0, n)
#define rep(...) ov(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define fec(...) for(const auto& __VA_ARGS__)
#define per(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)

#define ALL(x) begin(x), end(x)
#define SZ(x) (ll) size(x)
#define LB(v, x) (lower_bound(ALL(v), x) - begin(v))
#define eb emplace_back

bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
const ll INF = ll(4e18) + 100;

void printvec(const auto& v) {
   for(auto it = begin(v); it != end(v); it++) cout << *it << " ";
   cout << endl;
}

#ifdef LOCAL
#define local(...) __VA_ARGS__
#else
#define local(...)
#endif

// 頂点: ODD (0), EVEN (1), 含まれる回文
// 順辺 (par, chi): 両側に 1 文字足してできる回文への辺
// 逆辺 (suf): 最大回文接尾辞への辺, EVEN -> ODD
template<int C = 26, char first = 'a'> struct Eertree {
   string s;
   vc<int> len{-1, 0}, suf{0, 0}, par{0, 0}, vs;
   vc<array<int, C>> chi;
   int cur = 1;  // 現在の文字列の最大回文接尾辞の頂点番号
   Eertree() : chi(2) { rep(i, 2) fill(ALL(chi[i]), -1); }
   int findpar(int v) {
      for(int i = s.size() - 1;; v = suf[v]) {
         int j = i - 1 - len[v];
         if(j >= 0 && s[j] == s[i]) return v;
      }
   }
   void add(char ch) {
      s += ch;
      int j = ch - first, p = findpar(cur), v = chi[p][j];
      if(v != -1) {
         vs.eb(cur = v);
         return;
      }
      vs.eb(chi[p][j] = cur = len.size());
      len.eb(len[p] + 2), par.eb(p);
      suf.eb(p == 0 ? 1 : chi[findpar(suf[p])][j]);
      chi.eb(), fill(ALL(chi.back()), -1);
   }
   // 各回文の出現回数
   vl count() {
      int n = len.size();
      vl cnt(n);
      fec(v : vs) cnt[v]++;
      per(i, n, 1) cnt[suf[i]] += cnt[i];
      return cnt;
   }
};

void main2()
{
  string S,T;
  cin>>S>>T;
  Eertree<28, 'A'> et;
  fec(c : S) et.add(c);
  vl f = et.count();
  et.add('A' + 26), et.add('A' + 27);
  fec(c : T) et.add(c);
  vl g = et.count();
  local(printvec(f), printvec(g));
  ll ans = 0;
  rep(i, 2, f.size()) ans += f.at(i) * (g.at(i) - f.at(i));
  cout<<ans<<endl;
}

int main() {
#ifndef LOCAL
   cin.tie(0)->sync_with_stdio(0), cout.tie(0);
#endif

   local(while(true)) {
      ll t = 1;
      // cin >> t;
      while(t--) main2();
   }
}
0