hdu2457 Trie图+dp-白红宇

hdu2457 Trie图+dp

阅读量：4309 次

发布时间：2019-06-06

本文共 3175 字，大约阅读时间需要 10 分钟。

给定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 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
              10 #include 
              
                11 #include 
               
                 12 #include 
                
                  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
                 
                   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 else113 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 }