题意是给定一系列模式串。然后给出一个文本串，问至少改变文本串里面多少个字符可以使文本串不包含任何一个模式串。
还是先建立Trie图，然后在Trie图上面进行dp。dp的思路也不是很复杂。dp[i][j]的意思是长度为i的文本串需要改变dp[i][j]个字符顺利到达状态j。需要注意的是长度为i的时候，对应的字符串中的第i-1个字符。刚开始一直没发现这个bug。而且注意中途不能转移到匹配成功的状态上去，多加几个条件控制即可了。。。转移方程，dp[i][j] = min(dp[i][j], dp[i-1][nNext] + szText[i-1] != k)，其中nNext是从状态j可以转移到的非匹配成功的状态，k代表的当前边的权。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
| #include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_N = 61;
const int MAX_L = 31;
const int MAX_D = 4;
const int INF = 1110;
char chHash[256];
char szPat[MAX_L];
void InitHash()
{
chHash['A'] = 0;
chHash['G'] = 1;
chHash['C'] = 2;
chHash['T'] = 3;
}
struct Trie
{
Trie* fail;
Trie* next[MAX_D];
bool flag;
int no;
};
int nP;
Trie* pRoot;
Trie tries[MAX_N * MAX_L];
Trie* NewNode()
{
memset(tries[nP], 0, sizeof(Trie));
tries[nP].no = nP;
return tries[nP++];
}
void InitTrie(Trie* pRoot)
{
nP = 0;
pRoot = NewNode();
}
void Insert(Trie* pRoot, char* pszPat)
{
Trie* pNode = pRoot;
while (*pszPat)
{
int idx = chHash[*pszPat];
if (pNode->next[idx] == NULL)
{
pNode->next[idx] = NewNode();
}
pNode = pNode->next[idx];
++pszPat;
}
pNode->flag = true;
}
void BuildAC(Trie* pRoot)
{
pRoot->fail = NULL;
queue<Trie*> qt;
qt.push(pRoot);
while (!qt.empty())
{
Trie* front = qt.front();
qt.pop();
for (int i = 0; i < MAX_D; ++i)
{
if (front->next[i])
{
Trie* pNode = front->fail;
while (pNode && pNode->next[i] == NULL)
{
pNode = pNode->fail;
}
front->next[i]->fail = pNode? pNode->next[i] : pRoot;
front->next[i]->flag |= front->next[i]->fail->flag;
qt.push(front->next[i]);
}
else
{
front->next[i] = front == pRoot? pRoot : front->fail->next[i];
}
}
}
}
int nChange[INF][INF];
char szText[INF];
int Solve()
{
int nLen = strlen(szText);
for (int i = 0; i <= nLen; ++i)
{
for (int j = 0; j < nP; ++j)
{
nChange[i][j] = INF;
}
}
int i, j, k;
nChange[0][0] = 0;
for (i = 1; i <= nLen; ++i)
{
for (j = 0; j < nP; ++j)
{
if (tries[j].flag) continue;
if (nChange[i - 1][j] == INF) continue;
for (k = 0; k < MAX_D; ++k)
{
int nNext = tries[j].next[k] - tries;
if (tries[nNext].flag) continue;
int nTemp = nChange[i - 1][j] + (k != chHash[szText[i - 1]]);
nChange[i][nNext] = min(nChange[i][nNext], nTemp);
}
}
}
int nAns = INF;
for (i = 0; i < nP; ++i)
{
if (!tries[i].flag)
nAns = min(nAns, nChange[nLen][i]);
}
return nAns == INF? -1 : nAns;
}
int main()
{
int nN;
int nCase = 1;
InitHash();
while (scanf("%d", &nN), nN)
{
InitTrie(pRoot);
while (nN--)
{
scanf("%s", szPat);
Insert(pRoot, szPat);
}
BuildAC(pRoot);
scanf("%s", szText);
printf("Case %d: %d\n", nCase++, Solve());
}
return 0;
}
|