読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

ARC 024 C - だれじゃ

AtCoder programming

問題

C: だれじゃ - AtCoder Regular Contest 024 | AtCoder

問題概要

長さnの文字列sがある.この中から長さkの連続する部分文字列を2つ取り出して,アナグラムになっている位置があるかどうか判定せよ.

  •  1 \le n \le 10^5
  •  1 \le k \le n

イデア

文字列内の文字はアルファベット小文字のみなので26種類になる.そして,この26種類について現れた回数の累積和を持っておくことによってi文字目から始まる部分列とj文字目から始まる部分列がアナグラムになっているかどうかをO(1)で判定可能になる.よってこの方法は全体でO(n^2)の計算量となるが,これでは制約上不十分である.

さて,今答えるべきものはアナグラムになるような部分列の組が存在するか否かということであるので,i文字目とj文字目という情報は必要ない.そこで,この累積和の情報を文字列に起こすことにする.多くても累積和の1つの値は100000となるので,「26種類に対して6桁のスペースをそれぞれ用意してそれらを全て連結したもの」をi文字目から始まる部分列として表すことにしよう.例を上げれば,今見ている部分列がadbだったときには,0000010000010000000000010...0のような符号化をする.

そして,得られる全ての部分文字列を符号化した後にソートすると,隣り合っている部分が一致しているかどうかを判定することでアナグラム判定をすることができる.これで計算量はO(nlogn)となって,問題は解けた.また,判定の際にただ同じものが判定するだけではなく,部分文字列が文字列s上でかぶっていてはいけないことに注意が必要である.

と思っていたのだが,この実装よりもそのまま累積和を利用したvectorをキーにしてソートした方が圧倒的に早かった.まあstringに変換するのムダが多いしそれはそうかと言う感じもする(stringに変換したsubmission).こちらは1329ms要したが,以下の実装は259msで通ったし,もう少しvectorを信じよう...

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef vector<int> vi;
typedef pair<vi,int> P;

int ct[100001][26]={0};

int main()
{
    int n,k;
    string s;
    cin >>n >>k >>s;

    int S=s.size();

    rep(i,S)
    {
        rep(j,26) ct[i+1][j]=ct[i][j];
        ++ct[i+1][s[i]-'a'];
    }

    vector<P> candidate;
    for(int i=k; i<=S; ++i)
    {
        vector<int> t(26);
        rep(j,26) t[j]=ct[i][j]-ct[i-k][j];
        candidate.pb( P(t,i-k) );
    }
    sort(all(candidate));

    string ans="NO";
    if(k<n)
    {
        int C=candidate.size();
        int st=0;
        for(int i=1; i<C; ++i)
        {
            if(candidate[st].fi == candidate[i].fi)
            {
                if(abs(candidate[st].se - candidate[i].se)>=k)
                {
                    ans="YES";
                    break;
                }
            }
            else st=i;
        }
    }
    cout << ans << endl;
    return 0;
}