VK Cup 2015 Round 2 : F. Encoding

本番中FFTが頭に浮かんだけど全然違った。
http://codeforces.com/contest/533/problem/F

問題

文字列Tをエンコードするとは、幾つかのアルファベットの対(同じアルファベットは2箇所以上に登場しない)に対し、T中でそれら対に含まれる文字をもう片方の文字に置き換えたものにすることをいう。

ここで文字列S,Tが与えられる。
Sの連続部分文字列S[i..(i+|T|-1)]のうち、任意のアルファベットの対の集合を用いてエンコードすることでTに出来るようなものを求め、iを列挙せよ。

解法

Sにおいて、あるアルファベットaのみを'1'、残りを'0'にしたものS(a)を考える。
(アルファベット毎に26通り考えられる)
同様にTに置いて26通りアルファベットbのみを'1'にしたT(b)を考える。

S[i..(i+|T|-1)]がTにエンコード可能であるならば、各アルファベットaに対し、S(a)[i..(i+|T|-1)]がT(b)と一致し、かつ逆にS(b)[i..(i+|T|-1)]がT(a)と一致するような(a,b)の組み合わせが作れることを判定すればよい。

S(a)[i..(i+|T|-1)]とT(b)の一致判定はZ algorithmでも理論上はできるが、|S|、|T|が大きいのでギリギリTLEしてしまい間に合わない。
下記のコードではローリングハッシュを用いて一致判定を行った。

struct RollingHash {
	static const ll mo0=1000000007,mo1=1000000009;
	static const ll mul0=10009,mul1=10007;
	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(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);
	}
	pair<ll,ll> hash(int l,int r) { // s[l..r]
		if(l>r) return make_pair(0,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 make_pair((hash_[0][r+1]+(mo0-hash_[0][l]*pmo[0][r+1-l]%mo0))%mo0,
			             (hash_[1][r+1]+(mo1-hash_[1][l]*pmo[1][r+1-l]%mo1))%mo1);
	}
	pair<ll,ll> hash(string s) { init(s); return hash(0,s.size()-1); }
	static pair<ll,ll> concat(pair<ll,ll> L,pair<ll,ll> R,int RL) { // hash(L+R) 
		while(pmo[0].size()<RL+2) pmo[0].push_back(pmo[0].back()*mul0%mo0), pmo[1].push_back(pmo[1].back()*mul1%mo1);
		return make_pair((R.first + L.first*pmo[0][RL])%mo0,(R.second + L.second*pmo[1][RL])%mo1);
	}
};
vector<ll> RollingHash::pmo[2];

int LS,LT;
string S,T;
pair<ll,ll> SH[26][202000],TH[26];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>LS>>LT>>S>>T;
	
	FOR(x,26) {
		s = string(LS,'0');
		FOR(i,LS) if(S[i]=='a'+x) s[i]='1';
		RollingHash sh;
		sh.init(s);
		FOR(i,LS-LT+1) SH[x][i]=sh.hash(i,i+LT-1);
		
		s = string(LT,'0');
		FOR(i,LT) if(T[i]=='a'+x) s[i]='1';
		sh.init(s);
		TH[x]=sh.hash(0,LT-1);
	}
	
	vector<int> R;
	FOR(i,LS-LT+1) {
		int vis[26]={};
		int ng=0;
		FOR(x,26) if(vis[x]==0) {
			FOR(y,26) if(vis[x]+vis[y]==0) {
				if(TH[y]==SH[x][i] && TH[x]==SH[y][i]) vis[x]=vis[y]=1;
			}
			if(vis[x]==0) {
				ng=true;
				break;
			}
		}
		if(!ng) R.push_back(i+1);
	}
	
	_P("%d\n",R.size());
	FORR(r,R) _P("%d ",r);
	_P("\n");
	
}

まとめ

Z algorithmで間に合わないのが意外だった。
掛算やmodを取りまくるローリングハッシュの方が速いとはねぇ。