HDU2457.cpp

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

int n, idx;

#define pb push_back
const int N = 1010, INF = 1e9;
int mp[128];

namespace ACAM {
    int tr[N][4], fail[N], dp1[N], dp2[N], mark[N], idx;
    vector<int> g[N];

    void init() {
        for (int i = 0; i <= idx; i++) {
            memset(tr[i], 0, sizeof tr[i]);
            fail[i] = 0;
            mark[i] = 0;
            dp1[i] = INF;
            vector<int>().swap(g[i]);
        }
        dp1[0] = 0;
        idx = 0;
    }

    void insert(const string& s) {
        int u = 0;
        for (char c: s) {
            int p = mp[c];
            if (!tr[u][p]) tr[u][p] = ++idx;
            u = tr[u][p];
        }
        mark[u] = 1;
    }

    void dfs(int u, int m) {
        mark[u] |= m;
        for (int to: g[u]) {
            dfs(to, m | mark[u]);
        }
    }

    void build() {
        queue<int> q;
        for (int i = 0; i < 4; i++) if (tr[0][i]) q.push(tr[0][i]);
        while (q.size()) {
            int fa = q.front(); q.pop();
            for (int i = 0; i < 4; i++) {
                int& u = tr[fa][i];
                if (u) fail[u] = tr[fail[fa]][i], q.push(u);
                else u = tr[fail[fa]][i];
            }
        }
        for (int i = 1; i <= idx; i++) {
            g[fail[i]].pb(i);
        }
        dfs(0, 0);
    }

    void update(int p) {
        for (int i = 0; i <= idx; i++) dp2[i] = INF;

        for (int u = 0; u <= idx; u++) {
            if (mark[u]) continue;
            for (int i = 0; i < 4; i++) {
                int to = tr[u][i];
                if (mark[to]) continue;
                if (i == p) dp2[to] = min(dp2[to], dp1[u]);
                else dp2[to] = min(dp2[to], dp1[u] + 1);
            }
        }

        for (int i = 0; i <= idx; i++) dp1[i] = dp2[i];
    }

    int getans() {
        int ans = INF;
        for (int i = 0; i <= idx; i++) ans = min(ans, dp1[i]);
        return ans >= INF ? -1 : ans;
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    mp['A'] = 0;
    mp['T'] = 1;
    mp['G'] = 2;
    mp['C'] = 3;

    for (int cases = 1; ; cases++) {
        cin >> n;
        if (n == 0) break;

        ACAM::init();
        string s;
        for (int i = 1; i <= n; i++) {
            cin >> s;
            ACAM::insert(s);
        }
        ACAM::build();
        
        cin >> s;
        for (char c: s) ACAM::update(mp[c]);
        cout << "Case " << cases << ": " << ACAM::getans() << '\n';
    }
    return 0;
}