hdu2457 Trie圖+dp

hdu2457

給定n個模式串，和一個文本串

問如果修改最少的字符串使得文本串不包含模式串，?

輸出最少的次數，如果不能修改成功，則輸出-1

dp[i][j] 表示長度為i的字符串，到達狀態j（Trie圖中的結點）所需要修改的最少次數

那么dp[0->n][0->size] = INF , ?dp[0][root] = 0, ?n代表字符串長度， size代表狀態數

那么答案就是 ?min{dp[n][size]}

我們根據模式串所建的Trie圖，進行模擬構造不包含模式串的字符串

從第一個字符串開始構造，依次遞增，在構造此字符的同時，比較是否和輸入串的該字符串相等，

如果相等，則表示該位置的字符不需要改變，如果不同，則表示該位置的字符需要改變

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <queue>
  7 #include <stack>
  8 #include <vector>
  9 #include <map>
 10 #include <set>
 11 #include <string>
 12 #include <math.h>
 13 using namespace std;
 14 #pragma warning(disable:4996)
 15 typedef long long LL;                   
 16 const int INF = 1<<30;
 17 /*
 18 
 19 */
 20 struct Node
 21 {
 22     int fail, next[4];
 23     bool isWord;
 24     void init()
 25     {
 26         fail = -1;
 27         isWord = false;
 28         for (int i = 0; i < 4; ++i)
 29             next[i] = -1;
 30 
 31     }
 32 }Trie[1000 + 10];
 33 int size;
 34 char str[1000 + 10];
 35 int dp[1000 + 10][1000 + 10];
 36 int getCode(char ch)
 37 {
 38     if (ch == 'A')
 39         return 0;
 40     if (ch == 'G')
 41         return 1;
 42     if (ch == 'C')
 43         return 2;
 44     return 3;
 45 }
 46 void insert(int root, char str[])
 47 {
 48     int cur = root;
 49     for (int i = 0; str[i]; ++i)
 50     {
 51         int idx = getCode(str[i]);
 52         if (Trie[cur].next[idx] == -1)
 53         {
 54             Trie[size].init();
 55             Trie[cur].next[idx] = size++;
 56         }
 57         cur = Trie[cur].next[idx];
 58     }
 59     Trie[cur].isWord = true;
 60 }
 61 void makeFail(int root)
 62 {
 63     queue<int> q;
 64     int cur;
 65     for (int i = 0; i < 4; ++i)
 66     if (Trie[root].next[i] == -1)
 67         Trie[root].next[i] = root;
 68     else
 69     {
 70         Trie[Trie[root].next[i]].fail = root;
 71         q.push(Trie[root].next[i]);
 72     }
 73     while (!q.empty())
 74     {
 75         cur = q.front();
 76         q.pop();
 77         for (int i = 0; i < 4; ++i)
 78         {
 79             if (Trie[Trie[cur].fail].isWord)
 80                 Trie[cur].isWord = true;
 81             if (Trie[cur].next[i] == -1)
 82                 Trie[cur].next[i] = Trie[Trie[cur].fail].next[i];
 83             else
 84             {
 85                 Trie[Trie[cur].next[i]].fail = Trie[Trie[cur].fail].next[i];
 86                 q.push(Trie[cur].next[i]);
 87             }
 88         }
 89     }
 90 }
 91 
 92 //dp[i][j] 表示長度為i的字符串到達狀態j，所要修改的次數，  如果狀態為危險狀態，那么肯定是INF
 93 int solve(int root, char *str)
 94 {
 95     int n = strlen(str);
 96     for (int i = 0; i <= n; ++i)
 97     for (int j = 0; j < size; ++j)
 98         dp[i][j] = INF;
 99 
100     dp[0][root] = 0;
101     for (int i = 0; i < n; ++i)
102     for (int j = 0; j < size; ++j)
103     if (dp[i][j] < INF)
104     {
105         for (int k = 0; k < 4; ++k)
106         {
107             int next = Trie[j].next[k];
108             if (Trie[next].isWord) continue;
109             int tmp;
110             if (k == getCode(str[i]))
111                 tmp = dp[i][j];//如果構造出的字符和輸入字符相同，就不需要改變該位置的字符串
112             else
113                 tmp = dp[i][j] + 1;//否則，要改變該位置的字符串
114             dp[i + 1][next] = min(dp[i + 1][next], tmp);
115         }
116     }
117     int ans = INF;
118     for (int j = 0; j < size; ++j)
119         ans = min(ans, dp[n][j]);
120     if (ans == INF) ans = -1;
121     return ans;
122 }
123 
124 int main()
125 {
126     int n, k = 1;
127     char segment[20+10];
128     while(scanf("%d", &n), n)
129     {
130         Trie[0].init();
131         Trie[0].fail = 0;
132         size = 1;
133         for (int i = 0; i < n; ++i)
134         {
135             scanf("%s", segment);
136             insert(0, segment);
137         }
138         makeFail(0);
139         scanf("%s", str);
140         printf("Case %d: %d\n", k, solve(0, str));
141         k++;
142 
143     }
144     return 0;
145 }

轉載于:https://www.cnblogs.com/justPassBy/p/4593976.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/273175.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/273175.shtml
英文地址，請注明出處：http://en.pswp.cn/news/273175.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！