SRM563 div2 easy FoxAndHandleEasy

文字列Sがあり、その文字列Sの任意の位置に同じ文字列Sを挿入する。そうして作られる文字列をSのexpansionと呼ぶとする。文字列S, Tが与えられたとき、TがSのexpansionかどうかを求める問題。

コンテスト中に書いたコードは以下。std::stringの文字列の削除のやり方がすぐに分からず、Dashで調べながら小さなプログラムを書いて確認しようかなと思ったけど逆に時間がかかりそうだったので止めました。

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

class FoxAndHandleEasy {
public:
    string isPossible( string S, string T ) {
        const int n = S.length();
        if (n*2 != T.length()) return "No";

        for (int i = 0; i < (int)T.length(); i++) {
            if (i+n >= T.length()) break;

            bool ok = true;
            for (int j = 0; j < n; j++) {
                if (S[j] != T[j+i]) {
                    ok = false;
                    break;
                }
            }

            if (!ok) continue;
            int p = 0;
            for (int j = 0; j < (int)T.length(); j++) {
                if (i <= j && j < i+n) continue;

                if (S[p++] != T[j]) {
                    ok = false;
                    break;
                }
            }

            if (ok) return "Yes";
        }
        return "No";
    }
};

Challenge phaseで他の人のコードを読むと、単純に文字列Sを検索して、見つかったらそれを削除して残りがSに等しいかを確認しているコードが殆どでした。ミスしてそうなコードは見当たらず、そのままChallenge phaseは終わりました。System Testが始まり、多くの人がこの問題を落としていて何事かと思ったら、以下のようなケースで引っかかっていました。

S = aba
T = ababaa

最初に見つかる aba を削除すると残る文字列は baa になり、Sと一致しませんが、2番目に見つかる aba を削除すると残る文字列は aba となり、Sと等しくなります。つまり、削除する文字列の位置が重要なんですね。これは気づきませんでした(気づかずに、Tに含まれる全てのSを検索するようなコードを書いていました)。

コンテスト後に書き直したコード:

class FoxAndHandleEasy {
public:
    string isPossible( string S, string T ) {
        string::size_type p = 0;
        while (string::npos != (p = T.find(S, p))) {
            string x = T.substr(0, p) + T.substr(p+S.length());
            if (x == S) return "Yes";
            p++;
        }
        return "No";
    }
};