結果

問題 No.263 Common Palindromes Extra
コンテスト
ユーザー SSRS
提出日時 2022-08-31 04:06:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,210 ms / 2,000 ms
コード長 2,922 bytes
コンパイル時間 1,937 ms
コンパイル使用メモリ 185,428 KB
実行使用メモリ 63,752 KB
最終ジャッジ日時 2024-11-07 20:34:06
合計ジャッジ時間 6,114 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
const long long BASE = 123456789;
const long long M30 = ((long long) 1 << 30) - 1;
const long long M31 = ((long long) 1 << 31) - 1;
const long long MOD = ((long long) 1 << 61) - 1;
unsigned long long modulo(unsigned long long x){
  unsigned long long xu = x >> 61;
  unsigned long long xd = x & MOD;
  unsigned long long res = xu + xd;
  if (res >= MOD){
    res -= MOD;
  }
  return res;
}
unsigned long long mul(unsigned long long a, unsigned long long b){
  unsigned long long au = a >> 31;
  unsigned long long ad = a & M31;
  unsigned long long bu = b >> 31;
  unsigned long long bd = b & M31;
  unsigned long long mid = au * bd + ad * bu;
  unsigned long long midu = mid >> 30;
  unsigned long long midd = mid & M30;
  return modulo(au * bu * 2 + midu + (midd << 31) + ad * bd);
}
struct rolling_hash{
  vector<long long> POW, S;
  rolling_hash(string s){
    int N = s.size();
    POW.resize(N + 1);
    POW[0] = 1;
    for (int i = 0; i < N; i++){
      POW[i + 1] = mul(POW[i], BASE);
    }
    S.resize(N + 1);
    S[N] = 0;
    for (int i = N - 1; i >= 0; i--){
      S[i] = modulo(mul(S[i + 1], BASE) + s[i]);
    }
  }
  long long get(int L, int R){
    return modulo(S[L] + MOD - mul(S[R], POW[R - L]));
  }
};
vector<int> manacher(string &S){
  int N = S.size();
  vector<int> ans(N, 0);
  int i = 0, j = 0;
  while (i < N){
    while (i >= j && i + j < N && S[i - j] == S[i + j]){
      j++;
    }
    ans[i] = j;
    int k = 1;
    while (i >= k && i + k < N && k + ans[i - k] < j){
      ans[i + k] = ans[i - k];
      k++;
    }
    i += k;
    j -= k;
  }
  return ans;
}
unordered_map<unsigned long long, int> solve(string S){
  int N = S.size();
  string T = "$";
  for (int i = 0; i < N; i++){
    T += S[i];
    T += '$';
  }
  vector<int> A = manacher(T);
  rolling_hash RH(S);
  unordered_map<unsigned long long, int> mp;
  priority_queue<pair<int, int>> pq;
  for (int i = 1; i < N * 2; i++){
    int l = (i - A[i] + 2) / 2, r = (i + A[i] - 1) / 2;
    if (l < r){
      unsigned long long hash = RH.get(l, r);
      if (mp.count(hash) == 0){
        pq.push(make_pair(r - l, l));
      }
      mp[hash]++;
    }
  }
  while (!pq.empty()){
    int L = pq.top().second;
    int R = L + pq.top().first;
    pq.pop();
    unsigned long long hash = RH.get(L, R);
    L++;
    R--;
    if (L < R){
      unsigned long long hash2 = RH.get(L, R);
      if (mp.count(hash2) == 0){
        pq.push(make_pair(R - L, L));
      }
      mp[hash2] += mp[hash];
    }
  }
  return mp;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string S;
  cin >> S;
  string T;
  cin >> T;
  unordered_map<unsigned long long, int> A = solve(S);
  unordered_map<unsigned long long, int> B = solve(T);
  long long ans = 0;
  for (auto P : A){
    if (B.count(P.first) == 1){
      ans += (long long) P.second * B[P.first];
    }
  }
  cout << ans << endl;
}
0