問題概要

英小文字のみからなる 2 つの文字列 $S, T$ が与えられる。 $T$ は $S$ に英小文字を 1 つ挿入して作られたことがわかっている。

挿入された文字は $T$ の先頭から何番目の文字であるか求めよ。

複数の候補が考えられる場合はいずれか 1 つを求めよ。

制約

$1 \le |S| \le 10^{5}$

解法

挿入された文字を探し出すためには、次のように for 文を使って、 $S$ と $T$ を先頭から見ていき、はじめて文字が異なる場所を探せばよいでしょう。

int result = T.size();
for (int i = 0; i < S.size(); ++i) {
    if (S[i] != T[i]) {
        result = i + 1;  // 1-indexed にする
        break;
    }
}

これで、挿入された「異質な文字」が割り出せます。ただし、いくつかの注意点があります。

注意 1：S の末尾に挿入された場合

上のコードでは一つ妙なところがあります。それは

int result = T.size();

と初期化していることです。これは、S の末尾に小文字を挿入する場合に対処するためのものです。たとえば

$S$ = "abc"
$T$ = "abcg"

のように、 $S$ の末尾に文字を挿入することで $T$ が出来上がっている場合は、一度も if (S[i] != T[i]) の内部に入ることはありません。この場合の答えは $T$ の文字数を $M$ として $M$ となります。

よって、あらかじめ上に述べた初期化を実行することで、 $S$ の末尾に文字が挿入された場合にも対処できます。

注意 2：挿入箇所で S[i] != T[i] になるとは限らない

もう一つの注意点は、おそらくコンテスト中には多くの人が気づかなかったポイントではないかと思います。それでも正解できてしまうため、問題にはなりません。

たとえば、 $S$ = "abcd" に対して、3 文字目 ("ab" と "cd" の間) に文字 c を挿入してみましょう。このとき

$S$ = "abcd"
$T$ = "abccd"

となります。3 文字目に c を挿入したはずなのに、3 文字目はともに c になっています。一見不味いように思えるかもしれません。

しかしこの場合、代わりに $S$ の 4 文字目に c を挿入することによっても、同じ文字列 $T$ を作ることができます。

今回の問題では「複数の候補が考えられる場合はいずれか 1 つ求めよ」とのことなので、結局 if (S[i] != T[i]) となる最小の i を求めるコードで正解できます。

より正確な証明は公式解説に。

コード

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

int main() {
    string S, T;
    cin >> S >> T;

    int result = T.size();
    for (int i = 0; i < S.size(); ++i) {
        if (S[i] != T[i]) {
            result = i + 1;  // 1-indexed にする
            break;
        }
    }
    cout << result << endl;
}