これも凡ミスしたものの、何とか解ききれてよかった。
http://arc024.contest.atcoder.jp/tasks/arc024_3
問題
N文字の文字列Sが与えられる。
このうち、重ならない2つの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"); }
まとめ
文字列のハッシュ化、ライブラリ化しておこうかな。