中国建设银行悦生活网站,长沙移动网站建设哪家好,网站结构化数据,枣庄高端网站定制hdu2457 给定n个模式串#xff0c; 和一个文本串 问如果修改最少的字符串使得文本串不包含模式串#xff0c; 输出最少的次数#xff0c;如果不能修改成功#xff0c;则输出-1 dp[i][j] 表示长度为i的字符串#xff0c; 到达状态j#xff08;Trie图中的结点#xff09;… hdu2457 给定n个模式串 和一个文本串 问如果修改最少的字符串使得文本串不包含模式串 输出最少的次数如果不能修改成功则输出-1 dp[i][j] 表示长度为i的字符串 到达状态jTrie图中的结点所需要修改的最少次数 那么dp[0-n][0-size] INF , dp[0][root] 0, n代表字符串长度 size代表状态数 那么答案就是 min{dp[n][size]} 我们根据模式串所建的Trie图 进行模拟构造不包含模式串的字符串 从第一个字符串开始构造依次递增在构造此字符的同时比较是否和输入串的该字符串相等 如果相等则表示该位置的字符不需要改变 如果不同则表示该位置的字符需要改变 1 #include stdio.h2 #include string.h3 #include stdlib.h4 #include algorithm5 #include iostream6 #include queue7 #include stack8 #include vector9 #include map10 #include set11 #include string12 #include math.h13 using namespace std;14 #pragma warning(disable:4996)15 typedef long long LL; 16 const int INF 130;17 /*18 19 */20 struct Node21 {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 queueint 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 else69 {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 else84 {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所要修改的次数 如果状态为危险状态那么肯定是INF93 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[2010];
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
