POJ. 3691 DNA repair

1.Problem
http://poj.org/problem?id=3691

2.Idea
Here

3.Source

 const int MAXK = 1000;  
 const int MAXLEN = 1010;  
 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;  
 }