HackerRank University CodeSprint 4 : D. Maximum Permutation

終盤ゴリ押しでパーカー圏内。
https://www.hackerrank.com/contests/university-codesprint-4/challenges/maximum-permutation

問題

２つの文字列W,Sが与えられる。
Sの部分列のうち長さが|W|となるものを列挙したとする。
それらのうちWのpermutationであるもののうち登場頻度が最大の物を求めよ。

もし頻度が等しいものが複数あるなら、辞書順最小のものを求めよ。

解法

まず頻度の数え上げに関してはRollingHashの要領で部分文字列内の各アルファベットの登場回数が同じものを数え上げる。
あとは頻度が等しいもののうち辞書順最小のものを求めればよい。
これは先にSuffixArrayを構築することで、どの位置を先頭とするものが辞書順で小さいかわかる。

struct RollingHash {
	static const ll mo0=1000000007,mo1=1000000009;
	static ll mul0,mul1;
	static const ll add0=1000010007, add1=1003333331;
	static vector<ll> pmo[2];
	string s; int l; vector<ll> hash_[2];
	void init(string s) {
		this->s=s; l=s.size(); int i,j;
		hash_[0]=hash_[1]=vector<ll>(1,0);
		if(!mul0) mul0=10009+(((ll)&mul0)>>5)%259,mul1=10007+(((ll)&mul1)>>5)%257;
		if(pmo[0].empty()) pmo[0].push_back(1),pmo[1].push_back(1);
		FOR(i,l) hash_[0].push_back((hash_[0].back()*mul0+add0+s[i])%mo0);
		FOR(i,l) hash_[1].push_back((hash_[1].back()*mul1+add1+s[i])%mo1);
	}
	ll hash(int l,int r) { // s[l..r]
		if(l>r) return 0;
		while(pmo[0].size()<r+2)
			pmo[0].push_back(pmo[0].back()*mul0%mo0), pmo[1].push_back(pmo[1].back()*mul1%mo1);
		return (((hash_[0][r+1]+(mo0-hash_[0][l]*pmo[0][r+1-l]%mo0))%mo0)<<32) | 
			             ((hash_[1][r+1]+(mo1-hash_[1][l]*pmo[1][r+1-l]%mo1))%mo1);
	}
};
vector<ll> RollingHash::pmo[2]; ll RollingHash::mul0,RollingHash::mul1;

struct SuffixArray {
	int N; vector<int> rank,lcp,sa,rsa; string S;
	
	SuffixArray(string S) : S(S){
		int i,h=0; vector<int> tmp;
		N=S.size(); rank.resize(N+1); sa.resize(N+1); tmp.resize(N+1);
		FOR(i,N+1) sa[i]=i, rank[i]=i==N?-1:S[i];
		
		for(int k=1; k<=N; k<<=1) {
			auto pred2 = [k,this](int& a,int &b)->bool{ return (((a+k<=N)?rank[a+k]:-1)<((b+k<=N)?rank[b+k]:-1));};
			auto pred = [pred2,k,this](int& a,int &b)->bool{ return (rank[a]!=rank[b])?(rank[a]<rank[b]):pred2(a,b);};
			int x=0;
			if(k!=1) for(i=1;i<N+1;i++) if(rank[sa[i]]!=rank[sa[x]]) sort(sa.begin()+x,sa.begin()+i,pred2), x=i;
			sort(sa.begin()+x,sa.end(),pred);
			FOR(i,N+1) tmp[sa[i]]=(i==0)?0:tmp[sa[i-1]]+pred(sa[i-1],sa[i]);
			swap(rank,tmp);
		}
		lcp.resize(N+1); rsa.resize(N+1);
		FOR(i,N+1) rsa[sa[i]]=i;
		FOR(i,N) {
			int j=sa[rsa[i]-1];
			for(h=max(h-1,0);i+h<N && j+h<N; h++) if(S[j+h]!=S[i+h]) break;
			lcp[rsa[i]-1]=h;
		}
	}
};


int T;
string W,S;
int NW,NS;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		RollingHash RHS;
		cin>>W>>S;
		NW=W.size();
		NS=S.size();
		
		SuffixArray sa(S);
		RHS.init(S);
		
		
		int cnt[26]={};
		FORR(c,W) cnt[c-'a']++;
		
		map<ll,int> num,first;
		for(i=NS-1;i>=0;i--) {
			cnt[S[i]-'a']--;
			if(i+NW<NS) cnt[S[i+NW]-'a']++;
			
			if(i+NW<=NS) {
				FOR(j,26) if(cnt[j]) break;
				if(j==26) {
					num[RHS.hash(i,i+NW-1)]++;
					first[RHS.hash(i,i+NW-1)]=i;
				}
			}
		}
		
		int cur=-1,ma=0;
		FORR(r,num) {
			if(r.second>ma || (r.second==ma && sa.rsa[cur]>sa.rsa[first[r.first]])) {
				cur=first[r.first];
				ma=r.second;
			}
		}
		if(cur==-1) {
			cout<<cur<<endl;
		}
		else {
			cout<<S.substr(cur,NW)<<endl;
		}
		
		
	}
}

まとめ

SuffixArrayを使う問題は苦手なのだが、さっくり解けて良かった。