AtCoder ABC 066 B - ss (6Q, 灰色, 200 点)

全探索に慣れよう！

• 問題へのリンク

問題概要

同じ文字列を二個連結してできるような文字列を「偶文字列」とよぶ。

与えられた偶文字列 について、末尾の文字を 1 文字以上消して作れる偶文字列のうち、その最大長を答えよ。

制約

• 

考えたこと

全探索しよう！　文字列 の先頭から何個とってくるかで全探索すると、次のようなコードが書ける。ただし、文字列 str が偶文字列かどうかを判定する関数 iseven() が実装されている状況を考える。

int res = 0;
for (int i = 1; i < S.size(); i++) {
    // 先頭から i 文字分をとった文字列
    string sub = S.substr(0, i);

    // sub が偶文字列ならば、res を更新
    if (iseven(sub)) res = max(res, i);
}

あとは、偶文字列かどうかを判定する関数 iseven() を実装すればよい。一般に、文字列 が偶文字列かどうかは次のように判定できる。

---

• まず、 の長さが奇数である場合は、偶文字列ではない
• の長さ が偶数であるとき、任意の に対して、 であるときに限り、偶文字列である

---

あとは、この解法を実装すればよい。次のコードのように書ける。

コード

#include <bits/stdc++.h>
using namespace std;

// 文字列 S が偶文字列かどうかを判定する
bool iseven(const string &S) {
    int N = S.size();

    // そもそも偶数長でないとダメ
    if (N % 2 == 1) return false;

    // i 文字目と i+N/2 文字目が同じことが偶文字列の条件
    for (int i = 0; i < N/2; i++) {
        if (S[i+N/2] != S[i]) return false;
    }

    // すべての条件を満たせば true
    return true;
}

int main() {
    string S;
    cin >> S;

    int res = 0;

    // 長さを順に試していく
    for (int i = 1; i < S.size(); i++) {
        // 先頭から i 文字分をとった文字列
        string sub = S.substr(0, i);

        // sub が偶文字列ならば、res を更新
        if (iseven(sub)) res = max(res, i);
    }
    cout << res << endl;
}