Codeforces Round #349 (Div. 1) A. Reberland Linguistics

問題

codeforces.com

文字列 s が与えられる。この文字列を以下のルールにしたがって区切る。

• まず s の最初の 5 文字以上の文字を作る。
• その後は, 長さを 2 か 3 にしながら区切る。区切る時, 直前に区切ってできた文字列と同じになってはならない。

この時, 長さ 2/3 で区切った文字列としてあり得るものをすべて列挙せよ。

解法

最初に dp[i][k] = [0, i) を, 最後の文字数が k になるように区切れるか, というのを dp で計算します。

その後, i = s.size() から逆に辿って行って区切った文字列を作れるのかをチェックします。

// dp[i][k]
// [0, i) は既に使った
// 直前で使った文字は k 文字
bool dp[10010][4];
bool already[10010][4];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 5; i <= n; i++) dp[i][0] = true;
    for (int i = 5; i <= n; i++) {
        for (int j = 0; j < 4; j++) if (dp[i][j]) {
            for (int k = 2; k <= 3; k++) {
                if (i+k>n) break;
                if (j==0) dp[i+k][k] = true;
                else {
                    string prev = s.substr(i-j, j);
                    string now = s.substr(i, k);
                    if (prev != now) dp[i+k][k] = true;
                }
            }
        }
    }
    set<string> S;
    queue<pii> que;
    for (int k = 2; k <= 3; k++) if (dp[n][k]) que.push(pii(n, k));
    while (!que.empty()) {
        pii now = que.front(); que.pop();
        int pos = now.first, len = now.second;
        int next = pos-len;
        S.insert(s.substr(next, len));
        for (int k = 2; k <= 3; k++) {
            if (dp[next][k] && s.substr(next-k, k) != s.substr(next, len)) {
                if (already[next][k]) continue;
                already[next][k] = true;
                que.push(pii(next, k));
            }
        }
    }
    cout << S.size() << endl;
    for (string t : S) cout << t << endl;
    return 0;
}