Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 280 C問題 Extra Character

AtCoder ABC280 ABC C問題 300 pts

問題

提出解答

問題の概要

2つの文字列 $S,T$ が与えられている. なお, $T$ は $S$ に英小文字を1つ追加して得られる文字列である.

では, その追加された文字列は $T$ において先頭から何番目か? (複数の候補が考えられる場合はそのうちの1つを求めれば良い).

制約

$1 \leq |S| \leq 5 \times 10^5$
$S$ は英小文字からなる文字列
$T$ は $S$ に英小文字を1つ追加して得られる文字列.

解法

解答としては, $S$ の末尾に ${\tt *}$ を追加した文字列を $S'$ とする.

このとき, $S'[i]=T[i]$ を満たすような最小の整数が答え (の1つ) である.

実際, このような $i$ は必ず存在する.