AtCoder Regular Contest 024 C - だれじゃ

問題

　長さの文字列の中から、長さの連続な部分文字列を重複が無いように二つ選んだ時、それらがアナグラムになっているようなものが元の文字列の中に存在するかを判定せよ。

解法

　長さの部分文字列が互いにアナグラムになるかどうかは、その中にどの文字が何回登場するかをカウントすれば求めることができる。

　まず先頭文字分についてどの文字が何回登場するかをカウントしたあとは、文字目の登場回数を1回増やし、文字目の登場回数を1回減らすというような操作で順番に文字目から文字目までのカウント、文字目から文字目までのカウントができていく。

　求めらこれらを、先頭の文字の位置と共にmapに入れて、最後に中身が一致し、先頭の文字の位置が以上離れているものが存在するかどうかを判定すれば良い。全体としてで求まる。

反省

　20分25秒(0WA)でAC。sizeが26ののvectorをそのままmapに突っ込むだけという雑な解法でなんか通ってしまった。いや、理屈から言ってそれが可能なら通るのは当たり前なんだけど、vectorがキーとしてどういう風に表されているかを知らないまま書いているのでSTLが優秀であるというだけの話になってしまっている。

　なにか適当なハッシュ関数を作るのかとも思ったが、衝突させない方法がわからなかったので断念。適当な幅を取って開番地法でもやれば通ったかどうか。まぁmapでできるなら別に変なことする必要はないわけだけど……。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, K;
    string S;
    cin >> N >> K >> S;

    vector<ll> num(26, 0);
    for (ll i = 0; i < K; i++) {
        num[S[i] - 'a']++;
    }

    map<vector<ll>, ll> max_index;
    map<vector<ll>, ll> min_index;

    max_index[num] = K - 1;
    min_index[num] = K - 1;

    for (ll i = K; i < N; i++) {
        num[S[i - K] - 'a']--;
        num[S[i] - 'a']++;
        max_index[num] = i;
        if (min_index[num] == 0) {
            min_index[num] = i;
        }
    }

    for (auto p : max_index) {
        if (min_index[p.first] != 0) {
            if (p.second - min_index[p.first] >= K) {
                cout << "YES" << endl;
                return 0;
            }
        }
    }
    cout << "NO" << endl;
}