📘

ABC 386 C 文字列の任意の場所での消去

に公開
C++
AtCoder
tech

問題概要

問題

文字列 S に対して、最大1回の操作（挿入・削除・置換）で文字列 T に一致させられるかを判定する問題です。

制約

  • 文字列 S と T の長さはそれぞれ最大 500,000。
  • 操作回数は K=1。

操作は以下のいずれかです：

  1. 任意の位置に任意の文字を挿入する。
  2. 任意の位置の文字を削除する。
  3. 任意の位置の文字を他の文字に変更する。

問題の考え方

1. 長さの条件

文字列 S と T の長さに応じて次の3つのケースに分類します：

  • 長さの差が1の場合：
    • S の1文字を削除して T に一致するか判定。
  • 長さが等しい場合：
    • S の1文字を置換して T に一致するか判定。
  • それ以外：
    • 操作1回では一致不可能。

2. 一致判定の方法

  • 文字列を比較：最初に異なる文字位置を見つける。
  • 削除・置換処理：必要な操作を行い、新しい文字列を生成して比較。
  • 計算量：文字列の長さが最大でも O(n) に抑える。

実装

以下が具体的なC++コードです：

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

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

  // t が s より長ければ入れ替える
  if (t.size() > s.size()) {
    swap(s, t);
  }

  // 長さが1だけ異なる場合
  if (s.size() - 1 == t.size()) {
    int c = 0;
    while (s[c] == t[c]) {
      c++;
    }
    for (int i = c; i < s.size() - 1; i++) {
      s[i] = s[i + 1];
    }
    s.pop_back();
    cout << (t == s ? "Yes" : "No") << endl;

  // 長さが等しい場合
  } else if (s.size() == t.size()) {
    int cnt = 0;
    for (int i = 0; i < t.size(); i++) {
      if (t[i] != s[i]) {
        cnt++;
      }
    }
    cout << (cnt <= 1 ? "Yes" : "No") << endl;

  // その他の場合
  } else {
    cout << "No" << endl;
  }

  return 0;
}

学習内容

文字列の消去はシフト後に末尾消去で行なえる

Discussion