AtCoder ARC #024 : C - だれじゃ

これも凡ミスしたものの、何とか解ききれてよかった。
http://arc024.contest.atcoder.jp/tasks/arc024_3

問題

N文字の文字列Sが与えられる。
このうち、重ならない２つのK文字の部分文字列を抜き出したとき、並べ替えて同じ文字列にすることができるか。

解法

まず、並べ替えて同じ文字列に出来るかどうかは、a～zの各文字数の累積和を事前に取っておけば、Kが大きくなっても(アルファベット数が定数として)O(1)でチェックできる。

これだけではまだ部分文字列がO(N)個あり比較にO(N^2)かかるのでTLEする。
先に部分文字列群のハッシュを取っておき、比較対象を絞り込んでおくと良い。

int N,K;
char S[100005];

ll mo[2]={1000000007,1000000009};
ll prime[]={10007,10009,10037,10039,10061,10067,10069,10079,10091,10093,10099,10103,10111,10133,10139,10141,10151,
10159,10163,10169,10177,10181,10193,10211,10223,10243,10247,10253,10259};
ll rev[2][26];

int SS[26][100005];

ll modpow(ll a, ll n, ll mo) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

map<pair<ll,ll>,vector<int> > MM;

void solve() {
	int f,i,j,k,l,x,y;
	
	FOR(i,26) rev[0][i]=modpow(prime[i],mo[0]-2,mo[0]);
	FOR(i,26) rev[1][i]=modpow(prime[i],mo[1]-2,mo[1]);
	
	cin>>N>>K>>S;
	if(K*2>N) return _P("NO\n");
	
	FOR(i,26) FOR(x,N) SS[i][x+1]=SS[i][x]+(S[x]=='a'+i);
	
	ll hash[2]={1,1};
	FOR(i,N) {
		hash[0]=hash[0]*prime[S[i]-'a']%mo[0];
		hash[1]=hash[1]*prime[S[i]-'a']%mo[1];
		if(i>=K) {
			hash[0]=hash[0]*rev[0][S[i-K]-'a']%mo[0];
			hash[1]=hash[1]*rev[1][S[i-K]-'a']%mo[1];
		}
		if(i>=K-1) MM[make_pair(hash[0],hash[1])].push_back(i-(K-1));
	}
	
	ITR(it,MM) {
		vector<int> VV=it->second;
		FOR(x,VV.size()) for(y=x+1;y<VV.size();y++) {
			if(VV[y]<VV[x]+K) continue;
			int ng=0;
			FOR(i,26) {
				if(SS[i][VV[x]+K]-SS[i][VV[x]]!=SS[i][VV[y]+K]-SS[i][VV[y]]) ng++;
			}
			if(ng==0) return _P("YES\n");
		}
	}
	return _P("NO\n");
}

まとめ

文字列のハッシュ化、ライブラリ化しておこうかな。