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

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

AtCoder AGC 006 A - Prefix and Suffix (200 点)

 N \le 100 なのでいくらでも何でもできるという感覚

問題へのリンク

問題概要

すぬけ君は次の条件を満たす文字列に興味があります。

  • 長さ  N 以上である。
  • 先頭  N 文字が文字列  s に一致する。
  • 末尾  N 文字が文字列  t に一致する。

条件を満たす文字列のうち、最も短いものの長さを求めてください。

制約

  •  1 \le N \le 100
  •  |s| = |t| = N

考えたこと

とりあえず s = "ABC", t = "MOC" とかのときは愚直に

  • s + t = "ABCMOC"

とすれば条件を満たした文字列になる。今回はより短いものを求める必要がある。上の "ABCMOC" の例だとこれ以上短いのは無理だが、例えば

  • s = "ABC"
  • t = "BCD"

なら

  • "ABCD"

が条件を満たす最短長の文字列になっている。"BC" のところがオーバーラップしている。より具体的には、

  • s の i 文字目からとったもの
  • t の前の方をとったもの

とがオーバーラップするような i の最小値を求めればよいことがわかる。 N \le 10^{5} とかだったらちょっと工夫しないといけないが、 N \le 100 なので愚直にやって OK

  • s の i 文字目からとったものは、s.substr(i) (これは N-i 文字)
  • t の前から N-i 文字とったものは、t.substr(0, N-i)

と表せるので、これらが等しくなるような最初の i を求めれば OK。substr をとったり、それを比較したりするのに  O(N) かかるので、全体として  O(N^{2}) となる。

#include <iostream>
#include <string>
using namespace std;

int N;
string s, t;

int solve() {
    for (int i = 0; i < N; ++i) {
        if (s.substr(i) == t.substr(0, N-i)) return i + N;
    }
    return N*2;
}
int main() {
    cin >> N >> s >> t;
    cout << solve() << endl;
}