結果

問題 No.263 Common Palindromes Extra
ユーザー chocoruskchocorusk
提出日時 2019-10-25 09:46:57
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,126 bytes
コンパイル時間 1,700 ms
コンパイル使用メモリ 130,768 KB
実行使用メモリ 63,856 KB
最終ジャッジ日時 2023-09-26 10:52:38
合計ジャッジ時間 7,348 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 124 ms
7,688 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 4 ms
4,380 KB
testcase_03 AC 435 ms
14,776 KB
testcase_04 TLE -
testcase_05 TLE -
testcase_06 AC 176 ms
8,908 KB
testcase_07 TLE -
testcase_08 TLE -
testcase_09 AC 1,975 ms
63,856 KB
testcase_10 AC 1,832 ms
63,796 KB
testcase_11 AC 1,942 ms
62,784 KB
権限があれば一括ダウンロードができます

ソースコード

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;
struct SuffixArray{
	int n, k;
	vector<int> rk, tmp, sa;
	string s;
	SuffixArray(string s):n(s.size()), s(s), rk(s.size()+1), tmp(s.size()+1), sa(s.size()+1){
		auto compare_sa=[&](int i, int j){
			if(rk[i]!=rk[j]) return rk[i]<rk[j];
			else{
				int ri, rj;
				if(i+k<=n) ri=rk[i+k];
				else ri=-1;
				if(j+k<=n) rj=rk[j+k];
				else rj=-1;
				return ri<rj;
			}
		};
		for(int i=0; i<=n; i++){
			sa[i]=i;
			if(i<n){
				rk[i]=s[i]-'A';
			}else{
				rk[i]=-1;
			}
		}
		for(k=1; k<=n; k<<=1){
			sort(sa.begin(), sa.end(), compare_sa);
			tmp[sa[0]]=0;
			for(int i=1; i<=n; i++){
				tmp[sa[i]]=tmp[sa[i-1]];
				if(compare_sa(sa[i-1], sa[i])) tmp[sa[i]]++;
			}
			rk=tmp;
		}
	}
	int operator[](const int &k) const{
		return sa[k];
	}
};
struct LCP{
    SuffixArray sa;
    vector<int> lcp;
    LCP(SuffixArray sa):sa(sa), lcp(sa.n){
        int h=0;
        lcp[0]=0;
        for(int i=0; i<sa.n; i++){
            int j=sa[sa.rk[i]-1];
            if(h>0) h--;
            for(; j+h<sa.n && i+h<sa.n; h++){
                if(sa.s[j+h]!=sa.s[i+h]) break;
            }
            lcp[sa.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=1; i<=n+m; i++){
		if(sa[i]<n){
			rd[1][i-1]=rs[1][sa[i]];
			rd[0][i-1]=rs[0][sa[i]];
		}else{
			rd[1][i-1]=rt[1][sa[i]-n-1];
			rd[0][i-1]=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]<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+1]<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