結果

問題 No.263 Common Palindromes Extra
ユーザー chocoruskchocorusk
提出日時 2019-10-25 10:47:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,631 ms / 2,000 ms
コード長 6,380 bytes
コンパイル時間 1,743 ms
コンパイル使用メモリ 139,544 KB
実行使用メモリ 69,192 KB
最終ジャッジ日時 2024-07-19 07:10:13
合計ジャッジ時間 10,966 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
#define MP make_pair
#define fi first
#define se second
#define ALL(a)  (a).begin(),(a).end()
struct SuffixArray{
  ll size;
  string s;
  vector<ll>data;
  SuffixArray(string S):size(S.size()),s(S){
    s += '$';
    vector<ll>input(s.size());
    for(ll i=0;i<s.size();i++)input[i] = s[i];
    data = induced_sort(input, 200);
    data.erase(data.begin());
  }
  vector<ll> induced_sort(vector<ll>t, ll kind){
    ll sz = t.size();
    vector<bool>ls(sz);//trueはL型,falseはS型
    for(ll i = sz-1;i>=0;i--){
      if(i==sz-1)ls[i] = false;
      else{
        if(t[i]!=t[i+1])ls[i] = (t[i] > t[i+1]);
        else ls[i] = ls[i+1];
      }
    }
    vector<ll>cnt(kind);
    for(ll i=0;i<sz;i++)cnt[t[i]]++;
    vector<P>lr(kind,MP(-1,-1));
    for(ll i=1;i<kind;i++){
      if(cnt[i]==0)lr[i] = lr[i-1];
      else lr[i] = make_pair(lr[i-1].se + 1, lr[i-1].se + cnt[i]);
    }
    vector<ll>lmsidx,ret(sz,-1);
    for(ll i=0;i<sz-1;i++){
      if(ls[i]&&!ls[i+1]){
        ret[lr[t[i+1]].fi+cnt[t[i+1]]-1]=i+1;
        cnt[t[i+1]]--;
        lmsidx.push_back(i+1);
      }
    }
    fill(ALL(cnt),0);
    for(ll i=0;i<sz;i++){
      if(ret[i]>=1&&ls[ret[i]-1]){
        ret[lr[t[ret[i]-1]].fi+cnt[t[ret[i]-1]]]=ret[i]-1;
        cnt[t[ret[i]-1]]++;
        if(i!=0&&!ls[ret[i]])ret[i]=-1;
      }
    }
    fill(ALL(cnt),0);
    for(ll i=sz-1;i>=1;i--){
      if(ret[i]>=1&&!ls[ret[i]-1]){
        ret[lr[t[ret[i]-1]].se-cnt[t[ret[i]-1]]]=ret[i]-1;
        cnt[t[ret[i]-1]]++;
      }
    }
    vector<ll>rev_lmsidx(sz,-1),lmsinput(lmsidx.size(),-1);
    for(ll i=0;i<lmsidx.size();i++)rev_lmsidx[lmsidx[i]] = i;
    ll kindnum=1; 
    lmsinput[rev_lmsidx[ret[0]]] = 1;
    vector<ll>comp(t.begin()+ret[0],t.end());
    for(ll i=1;i<sz;i++){
      if(ret[i]>=1&&ls[ret[i]-1]&&!ls[ret[i]]){
        vector<ll>tmp(t.begin()+ret[i],t.begin()+lmsidx[rev_lmsidx[ret[i]]+1]+1); 
        if(comp != tmp){
          kindnum++;
          comp = tmp;
        }
        lmsinput[rev_lmsidx[ret[i]]] = kindnum;
      }
    }
    vector<ll>output;
    if(kindnum==lmsidx.size()){
      output.assign(kindnum,-1);
      for(ll i=0;i<lmsinput.size();i++)output[lmsinput[i]-1]=i;
    }
    else output = induced_sort(lmsinput,kindnum+1);
    
    fill(ALL(cnt),0), fill(ALL(ret),-1);
    for(ll i=output.size()-1;i>=0;i--){
      ll tmp=lmsidx[output[i]];
      ret[lr[t[tmp]].se - cnt[t[tmp]]]=tmp;
      cnt[t[tmp]]++;
    }
    fill(ALL(cnt),0);
    for(ll i=0;i<sz;i++){
      if(ret[i]>=1&&ls[ret[i]-1]){
        ret[lr[t[ret[i]-1]].fi+cnt[t[ret[i]-1]]]=ret[i]-1;
        cnt[t[ret[i]-1]]++;
        if(i!=0&&!ls[ret[i]])ret[i]=-1;
      }
    }
    fill(ALL(cnt),0);
    for(ll i=sz-1;i>=1;i--){
      if(ret[i]>=1&&!ls[ret[i]-1]){
        ret[lr[t[ret[i]-1]].se-cnt[t[ret[i]-1]]]=ret[i]-1;
        cnt[t[ret[i]-1]]++;
      }
    }
    return ret;
  }
  ll operator[](const int &k) const{
    return data[k];
  }
};
struct LCP{
    SuffixArray sa;
    vector<int> lcp, rk;
    LCP(SuffixArray sa):sa(sa), lcp(sa.size), rk(sa.size+1){
		rk[sa.size]=0;
      	for(int i=0; i<sa.size; i++){
			rk[sa[i]]=i+1;
		}
        int h=0;
        lcp[0]=0;
        for(int i=0; i<sa.size; i++){
            int j=sa[rk[i]-2];
            if(h>0) h--;
            for(; j+h<sa.size && i+h<sa.size; h++){
                if(sa.s[j+h]!=sa.s[i+h]) break;
            }
            lcp[rk[i]-1]=h;
        }
    }
	int operator[](const int &k) const{
		return lcp[k];
	}
};
vector< int > manacher(const string &s) {
  vector< int > radius(s.size());
  int i = 0, j = 0;
  while(i < s.size()) {
    while(i - j >= 0 && i + j < s.size() && s[i - j] == s[i + j]) {
      ++j;
    }
    radius[i] = j;
    int k = 1;
    while(i - k >= 0 && i + k < s.size() && k + radius[i - k] < j) {
      radius[i + k] = radius[i - k];
      ++k;
    }
    i += k;
    j -= k;
  }
  return radius;
}

int main()
{
	int n, m;
	string s, t;
	cin>>s>>t;
	n=s.size(), m=t.size();
	string u=s+"a"+t;
	vector<vector<int>> rs(2, vector<int>(n)), rt(2, vector<int>(m));
	rs[1]=manacher(s), rt[1]=manacher(t);
	{
		string s0, t0;
		s0+='#';
		t0+='#';
		for(int i=0; i<n; i++){
			s0+=s[i];
			s0+='#';
		}
		for(int i=0; i<m; i++){
			t0+=t[i];
			t0+='#';
		}
		vector<int> rs0=manacher(s0), rt0=manacher(t0);
		for(int i=0; i<n; i++){
			rs[0][i]=rs0[2*i]/2;
		}
		for(int i=0; i<m; i++){
			rt[0][i]=rt0[2*i]/2;
		}
	}
	SuffixArray sa(u);
	LCP lcp(sa);
	vector<vector<int>> rd(2, vector<int>(n+m));
	for(int i=0; i<n+m; i++){
		if(sa[i]<n){
			rd[1][i]=rs[1][sa[i]];
			rd[0][i]=rs[0][sa[i]];
		}else{
			rd[1][i]=rt[1][sa[i]-n-1];
			rd[0][i]=rt[0][sa[i]-n-1];
		}
	}
	ll ans=0;
	auto solve=[&](auto solve, int l, int r)->void{
		if(l>r) return;
		int mid=(l+r)/2;
		vector<int> mnl(mid-l+1), mnr(r-mid+1);
		mnl[mid-l]=lcp[mid];
		for(int i=mid-1; i>=l; i--){
			mnl[i-l]=min(mnl[i+1-l], lcp[i]);
		}
		mnr[0]=lcp[mid];
		for(int i=mid+1; i<=r; i++){
			mnr[i-mid]=min(mnr[i-1-mid], lcp[i]);
		}
		for(int p=0; p<2; p++){
			vector<int> vls, vlt;
			vector<ll> sls, slt;
			for(int i=mid; i>=l; i--){
				int x=min(mnl[i-l], rd[p][i-1]);
				if(sa[i-1]<n) vls.push_back(x);
				else vlt.push_back(x);
			}
			sort(vls.begin(), vls.end());
			sort(vlt.begin(), vlt.end());
			sls.resize(vls.size()+1);
			slt.resize(vlt.size()+1);
			for(int i=0; i<vls.size(); i++){
				sls[i+1]=sls[i]+vls[i];
			}
			for(int i=0; i<vlt.size(); i++){
				slt[i+1]=slt[i]+vlt[i];
			}
			for(int i=mid; i<=r; i++){
				int x=min(mnr[i-mid], rd[p][i]);
				if(sa[i]<n){
					int k=lower_bound(vlt.begin(), vlt.end(), x)-vlt.begin();
					ans+=slt[k]+(ll)(vlt.size()-k)*x;
				}else{
					int k=lower_bound(vls.begin(), vls.end(), x)-vls.begin();
					ans+=sls[k]+(ll)(vls.size()-k)*x;
				}
			}
		}
		solve(solve, l, mid-1);
		solve(solve, mid+1, r);
	};
	solve(solve, 1, n+m-1);
	cout<<ans<<endl;
    return 0;
}
0