なのでいくらでも何でもできるという感覚
問題概要
すぬけ君は次の条件を満たす文字列に興味があります。
- 長さ 以上である。
- 先頭 文字が文字列 に一致する。
- 末尾 文字が文字列 に一致する。
条件を満たす文字列のうち、最も短いものの長さを求めてください。
制約
考えたこと
とりあえず 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; }