C 問題としてはかなりハードな問題であった。

問題へのリンク

問題概要

$N$ 個の文字列 $S_{1}, S_{2}, \dots, S_{N}$ のうち、文字列 $T$ との編集距離が 1 以下であるものの個数を求めよ。

なお、文字列 $S$ と文字列 $T$ の編集距離が 1 以下であるとは、以下のいずれかが成り立つことを指す。

$S = T$ である
$S$ に文字を 1 文字挿入することで $T$ に一致する
$S$ から文字を 1 個削除することで $T$ に一致する
$S$ の文字を 1 文字変更することで $T$ に一致する

制約

$N, |T| \le 5 \times 10^{5}$
$|S_{i}|$ の総和は $5 \times 10^{5}$ 以下

考えたこと：まず計算量に注意

計算量が $O(NT)$ などになってはダメなことに気をつけよう。つまり、文字列 $T$ 全体に対して for 文を回すような作業を $N$ 回やったらダメなのだ。しかし、各文字列 $S_{i}$ に対して、それぞれ for 文を回すのは大丈夫だ。なぜなら、 $|S_{i}$ の総和を $A$ として、 $A \le 5 \times 10^{5}$ であるからだ。

よって、各文字列 $S_{i}$ と文字列 $T$ の関係性を調べるとき、for 文を回すときは基本的には次のようなループを用いることに気をつけよう。

for (int j = 0; j < S[i].size(); ++j) {

}

これの代わりに for (int j = 0; j < T.size(); ++j) などとしてはならない。

各文字列 $S_{i}$ に対する判定

それでは、具体的な判定方法を考えていく。一般に、次の値を求めておくことにしよう。

$S_{i}$ と $T$ をそれぞれ先頭からみていったときに、連続で一致する文字の個数 $l$
$S_{i}$ と $T$ をそれぞれ末尾からみていったときに、連続で一致する文字の個数 $r$

これらを求めるのに要する計算量は、基本的に文字列 $S_{i}$ の方で for 文を 2 回回せばよくて、 $O(|S_{i}|)$ となる。

$S_{i} = T$ の判定

これが成り立つ条件は次のように記述できる。

S[i].size() == T.size() であること
l == T.size() であること

$S_{i}$ に文字を挿入して $T$ にできるか

これが成り立つ条件は次のように記述できる。

S[i].size() + 1 == T.size() であること
l + r == S[i].size() であること

$S_{i}$ から文字を削除して $T$ にできるか

これが成り立つ条件は次のように記述できる。

S[i].size() - 1 == T.size() であること
l + r == T.size() であること

$S_{i}$ の文字を 1 文字変更して $T$ にできるか

これが成り立つ条件は次のように記述できる。

S[i].size() == T.size() であること
l + r + 1 == T.size() であること

コード

以上の判定をすると計算量は $O(N + A + M)$ となる。

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

int main() {
    int N;
    string T;
    cin >> N >> T;
    vector<string> S(N);
    for (int i = 0; i < N; ++i) cin >> S[i];

    vector<int> res;
    for (int i = 0; i < N; ++i) {
        // S[i] と T の文字数が 2 文字以上異なっていたらダメ
        if (abs((int)S[i].size() - (int)T.size()) >= 2) continue;
        
        // S[i] の先頭からと末尾から T と一致する文字数を求める
        int pre = 0, suf = 0;
        for (pre = 0; pre < min(S[i].size(), T.size()); ++pre) {
            if (S[i][pre] != T[pre]) break;
        }
        for (suf = 0; suf < min(S[i].size(), T.size()); ++suf) {
            if (S[i][S.size()-1-suf] != T[T.size()-1-suf]) break;
        }
        
        if (pre + suf >= min(S.size(), T.size())) res.push_back(i);
        else if (S.size() == T.size() && pre + suf + 1 == S.size()) res.push_back(i);
    }
    cout << res.size() << endl;
    for (auto v : res) cout << v+1 << " ";
    cout << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 324 C - Error Correction (茶色, 300 点)

問題概要

制約

考えたこと：まず計算量に注意