[Codeforces] Educational Codeforces Round 94 (Rated for Div. 2) A. String Similarity

2020年9月8日

問題

方針

同じ長さの文字列 \( s \) と \( t \) が ‘similar’ である条件は、\( s_i = t_i \) となる整数 \( i \) が存在することです。

長さ \( 2n – 1 \) の文字列 \( s \) の長さ \( n \) の部分文字列を \( s(i, i + n – 1) \) と表します。このとき、\( n \) 個の部分文字列に対して ‘similar’ となる長さ \( n \) の文字列は文字が全て \( s_{n-1} \) であるものが考えられます。これは、\( n \) 個の部分文字列が必ず \( s_{n-1} \) という文字を含むからです。

コード