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

なのでいくらでも何でもできるという感覚

問題へのリンク

問題概要

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

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

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

制約

• 
• 

考えたこと

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

• s + t = "ABCMOC"

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

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

なら

• "ABCD"

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

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

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

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

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

#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;
}