結果

問題 No.263 Common Palindromes Extra
ユーザー beetbeet
提出日時 2018-11-07 13:00:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 359 ms / 2,000 ms
コード長 3,028 bytes
コンパイル時間 2,865 ms
コンパイル使用メモリ 225,448 KB
実行使用メモリ 177,996 KB
最終ジャッジ日時 2023-08-20 00:39:12
合計ジャッジ時間 5,105 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
51,024 KB
testcase_01 AC 18 ms
50,284 KB
testcase_02 AC 18 ms
50,480 KB
testcase_03 AC 38 ms
57,760 KB
testcase_04 AC 107 ms
57,960 KB
testcase_05 AC 133 ms
57,468 KB
testcase_06 AC 28 ms
51,324 KB
testcase_07 AC 246 ms
118,124 KB
testcase_08 AC 266 ms
117,524 KB
testcase_09 AC 359 ms
177,996 KB
testcase_10 AC 347 ms
177,868 KB
testcase_11 AC 100 ms
57,056 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct PalindromicTree{
  struct node{
    map<char,int> nxt;
    int len,suf,hei,app,cnt;
  };
  vector<node> v;
  vector<int> ord;
  int n,suff;
  PalindromicTree(){}
  PalindromicTree(const string &s){init(s);build(s);}
  bool addchar(const string &s,int pos){
    char ch=s[pos];
    int cur=suff;
    while(1){
      if(pos-1-v[cur].len>=0&&s[pos-1-v[cur].len]==ch) break;
      cur=v[cur].suf;
    }
    if(v[cur].nxt.count(ch)){
      suff=v[cur].nxt[ch];
      v[suff].cnt++;
      return false;
    }
    suff=n++;
    v[suff].len=v[cur].len+2;
    v[suff].app=pos-v[suff].len+1;
    v[suff].cnt=1;
    v[cur].nxt[ch]=suff;
    
    if(v[suff].len==1){
      v[suff].suf=1;
      v[suff].hei=1;
      return true;
    }
    while(1){
      cur=v[cur].suf;
      if(pos-1-v[cur].len>=0&&s[pos-1-v[cur].len]==ch){
        v[suff].suf=v[cur].nxt[ch];
        break;
      }
    }
    v[suff].hei=v[v[suff].suf].hei+1;
    return true;
  }
  
  void init(const string &s){
    v.resize(s.length()+10);

    n=2;
    suff=1;
    v[0].app=v[1].app=-1;
    v[0].len=-1;v[1].len=0;
    v[0].suf=v[1].suf=0;
    v[0].hei=v[1].hei=0;
  }
  
  void calcOrder(){
    ord.clear();
    ord.push_back(0);
    ord.push_back(1);
    for(int i=0;i<(int)ord.size();i++){
      for(auto &p:v[ord[i]].nxt) ord.push_back(p.second);
    }
  }
  
  void calcCount(){
    assert(ord.size());
    for(int i=(int)ord.size()-1;i>=0;i--){
      v[v[ord[i]].suf].cnt+=v[ord[i]].cnt;
    }
    v[0].cnt=v[1].cnt=0;
  }

  void build(const string &s){
    for(int i=0;i<(int)s.size();i++) addchar(s,i);
    calcOrder();
    calcCount();
    ord.clear();
    for(auto &x:v) x.nxt.clear();
    v.resize(n);
    v.shrink_to_fit();
  }
  
};

struct RollingHash{
  typedef unsigned int ull;
  static const ull B = 1777771;
  vector<ull> hash;
  static vector<ull> p;
  RollingHash(){}
  RollingHash(const string &S){
    int len=S.size();
    hash.assign(len+1,0);
    for(int i=0;i<len;i++) hash[i+1]=hash[i]*B+S[i];
  };
  static void ensure(int n){
    if((int)p.size()>=n) return;
    p.assign(n,1);
    for(int i=0;i+1<n;i++) p[i+1]=p[i]*B;
  }
  //S[l,r)
  ull find(int l,int r){
    return hash[r]-hash[l]*p[r-l];
  }
};
vector<RollingHash::ull> RollingHash::p;

using ll = long long;
using ull = RollingHash::ull;
signed main(){
  string s,t;
  cin>>s>>t;
  
  PalindromicTree p1(s),p2(t);
  RollingHash::ensure(max(s.size()+1,t.size()+1));  
  RollingHash r1(s),r2(t);
  
  const int MAX = 5e5+100;  
  map<ull, int> m1[MAX],m2[MAX];
  
  for(int i=0;i<(int)p1.n;i++){
    auto &u=p1.v[i];
    if(u.app<0) continue;
    m1[u.len][r1.find(u.app,u.app+u.len)]=u.cnt;
  }
  
  for(int i=0;i<(int)p2.n;i++){
    auto &u=p2.v[i]; 
    if(u.app<0||!m1[u.len].count(r2.find(u.app,u.app+u.len))) continue;
    m2[u.len][r2.find(u.app,u.app+u.len)]=u.cnt;
  }
  
  ll ans=0;
  for(int i=1;i<=(int)s.length();i++)
    for(auto p:m1[i]) ans+=(ll)m2[i][p.first]*(ll)p.second;
  
  cout<<ans<<endl;
  return 0;
}
0