結果

問題 No.263 Common Palindromes Extra
ユーザー beetbeet
提出日時 2018-11-07 12:38:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 2,758 bytes
コンパイル時間 2,385 ms
コンパイル使用メモリ 226,804 KB
実行使用メモリ 283,476 KB
最終ジャッジ日時 2024-11-20 20:40:10
合計ジャッジ時間 4,618 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
57,104 KB
testcase_01 AC 19 ms
50,404 KB
testcase_02 AC 18 ms
50,476 KB
testcase_03 AC 40 ms
68,356 KB
testcase_04 AC 105 ms
140,148 KB
testcase_05 AC 132 ms
140,092 KB
testcase_06 AC 30 ms
58,704 KB
testcase_07 MLE -
testcase_08 MLE -
testcase_09 MLE -
testcase_10 MLE -
testcase_11 AC 100 ms
140,008 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct PalindromicTree{
  struct node{
    map<char,int> nxt;
    int len,suf,hei,app,cnt;
  };
  string s;
  vector<node> v;
  vector<int> ord;
  int n,suff;
  PalindromicTree(){}
  PalindromicTree(string s_){init(s_);build();}
  bool addchar(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(string s_){
    s=s_;
    v.clear();
    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(){
    for(int i=0;i<(int)s.size();i++) addchar(i);
    calcOrder();
    calcCount();
  }
  
};

struct RollingHash{
  typedef unsigned long long ull;
  string S;
  ull B;
  vector<ull> hash,p;
  int len;
  RollingHash(){}
  RollingHash(string S,ull B=1000000007LL):S(S),B(B){init();};
  void init(){
    len=S.length();
    hash.resize(len+1);
    p.resize(len+1);
    hash[0]=0;p[0]=1;
    for(int i=0;i<len;i++){
      hash[i+1]=hash[i]*B+S[i];
      p[i+1]=p[i]*B;
    }
  }
  //S[l,r)
  ull find(int l,int r){
    return hash[r]-hash[l]*p[r-l];
  }
};


using ll = long long;
signed main(){
  string s,t;
  cin>>s>>t;
  PalindromicTree p1(s),p2(t);
  RollingHash r1(s),r2(t);
  const int MAX = 5e5+100;
  map<int, ll> m1[MAX],m2[MAX];
  for(int i=0;i<(int)p1.n;i++){
    PalindromicTree::node& 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++){
    PalindromicTree::node& u=p2.v[i]; 
    if(u.app<0) 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+=m2[i][p.first]*p.second;
    }
  }
  cout<<ans<<endl;
  return 0;
}
0