POJ 3691 DNA repair

蟻本の文字列の章読んでたら出てきたので解きました。POJ めっちゃ久しぶりや…　前やった SRM の問題に似てます。mayokoex.hatenablog.com

問題

3691 -- DNA repair

解法

蟻本に書いてあるとおり。

const int MAXK = 1000;
const int MAXLEN = 1010;
const int INF = 1e8;
const string AGCT = "AGCT";
int nextState[MAXK][4];
bool ng[MAXK];
int dp[MAXLEN][MAXK];

int solve(const vector<string>& ngWords, const string& init) {
    vector<string> pfx;
    int n = ngWords.size();
    // 状態の列挙
    for (int i = 0; i < n; i++) {
        string s = ngWords[i];
        for (int j = 0; j <= (int)s.size(); j++) {
            pfx.push_back(s.substr(0, j));
        }
    }
    sort(pfx.begin(), pfx.end());
    pfx.erase(unique(pfx.begin(), pfx.end()), pfx.end());
    int K = pfx.size();
    // 状態の遷移
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < 4; j++) {
            string s = pfx[i] + AGCT.substr(j, 1);
            while (1) {
                int nk = lower_bound(pfx.begin(), pfx.end(), s) - pfx.begin();
                if (nk < K && pfx[nk] == s) {
                    nextState[i][j] = nk;
                    break;
                }
                s = s.substr(1);
            }
        }
    }
    // 状態がngかどうか
    for (int i = 0; i < K; i++) {
        ng[i] = false;
        int sl = pfx[i].size();
        for (int j = 0; j < n; j++) {
            int wl = ngWords[j].size();
            if (sl < wl) continue;
            if (pfx[i].substr(sl-wl) == ngWords[j]) {
                ng[i] = true;
                break;
            }
        }
    }
    // dp
    int length = init.size();
    for (int i = 0; i <= length; i++) for (int k = 0; k < K; k++) {
        dp[i][k] = INF;
    }
    dp[0][0] = 0;
    for (int l = 0; l < length; l++) for (int k = 0; k < K; k++) {
        if (dp[l][k] == INF) continue;
        if (ng[k]) continue;
        for (int j = 0; j < 4; j++) {
            int plus = (init[l] == AGCT[j]) ? 0 : 1;
            int ns = nextState[k][j];
            if (ng[ns]) continue;
            dp[l+1][ns] = min(dp[l][k]+plus, dp[l+1][ns]);
        }
    }
    int ans = INF;
    for (int k = 0; k < K; k++) {
        if (ng[k]) continue;
        ans = min(ans, dp[length][k]);
    }
    if (ans == INF) ans = -1;
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T = 0;
    int n;
    while (cin >> n) {
        if (n == 0) break;
        T++;
        vector<string> ngWords;
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            ngWords.push_back(s);
        }
        string init;
        cin >> init;
        printf("Case %d: %d\n", T, solve(ngWords, init));
    }
    return 0;
}