Hatena::Grouptopcoder

yaottiの日記

2010-03-11

SRM 156 DIV2続き

| 16:24

hard

TopCoder Statistics - Problem Statement

greedyに一致させていくと最適にならないケース(問題のsample5)にどう対処すればいいのかわからない…

例えば

original: ABABCDC

compound: ABABABC

だと,greedyにやるとABAB+AB+Cで3になるけど,うまくやればAB+ABABCで2になる.

後者の方が良いと知る方法はあるのかな.全部試すしかない気がする…

class WordParts {
public:
    int partCount(string original, string compound) {
        int result = 0;
        int idx = 0;
        int len = compound.size();
        while (idx < len) {
            int i = 0;
            for (; i < (int)original.size(); i++) {
                if (original[i] != compound[idx+i]) break;
            }
            int j = 0;
            int maxj = 0;
            for (int idxj = 1; idxj < (int)compound.size()-idx+1; idxj++) {
                string s = compound.substr(idx,idxj); // 残っているcompoundから切り取っていく
                // 文字列が見付からないならそこで終了
                if (original.find(s, 1) == string::npos) break;
                int pos = 1;    // 検索開始位置,最後尾の物を得る
                while (original.find(s, pos) != string::npos) {
                    j = original.find(s, pos);
                    pos++;
                }
                // 末尾に一致しなければ,失敗
                if (j + idxj != (int)original.size()) {
                    continue;
                }
                maxj = max(idxj, maxj);
            }
            if (i == 0 && maxj == 0) return -1;
            result++;
            idx += max(i,maxj);
        }
        return result;
    }
}