HDU - 2457
题意：最少改变多少个字符，使给定的字符串不包含以上的任意一个字串。
题解
dp[i][j]表示在第字符串的第i个位置，在第j个结点，不包含任意一个字串的最少改变次数。初始化为inf,dp[0][0] = 0;我们状态转移是有顺序的从root结点和0号位置开始的。fail树相当于从root开始一层一层的往外扩展，类似与bfs。如果我们在字符串的第i个位置，从j号结点向外扩展，首先要判断第i-1个位置是否到达j号结点，即判断dp[i-1][j]是否为inf，如果为inf，就不能从这个dp[i-1][j]开始转移。然后枚举j号结点可以向外扩展的结点，如果是危险结点，那么不能扩展。设向外扩展的结点为k，对应的字符为ss，那么dp[i][k] = min(dp[i][k],dp[i-1][j] + ss != s[i])。最后求min（dp[len][01…]）
代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
int const inf = 0x3f3f3f3f;
int const M = 500000+ 10;
int const N = 1000 + 10;
int tot;
struct Node{
Node *next[4];
Node *fail;
int cnt; //判断是否是结尾，即危险结点
int index; //结点的标号
Node(){
for(int i=0;i<4;i++) next[i] = NULL;
fail = NULL;
cnt = 0;
index = tot++;
}
}*q[M],*root,*trie[N];
int getnum(char s){
if(s == 'A') return 0;
else if(s == 'C') return 1;
else if(s == 'T') return 2;
else return 3;
}
void Insert(char *s){
int n = strlen(s);
Node *now = root;
for(int i=0;i<n;i++){
int to = getnum(s[i]);
if(now->next[to] == NULL){
now->next[to] = new Node();
trie[tot-1] = now->next[to];
}
now = now->next[to];
}
now->cnt = 1;
}
void Get_Fail(){
int head = 0,tail = 0;
q[head++] = root;
root->fail = NULL;
while(head != tail){
Node *tmp = q[tail++];
Node *p;
for(int i=0;i<4;i++){
if(tmp->next[i] == NULL){ //空指针
if(tmp == root) tmp->next[i] = root;
else tmp->next[i] = tmp->fail->next[i];
continue;
}
if(tmp == root) tmp->next[i]->fail = root;
else{
p = tmp->fail;
while(p){
if(p->next[i]){
tmp->next[i]->fail = p->next[i];
if(tmp->next[i]->fail->cnt) tmp->next[i]->cnt = 1; //包含关系
break;
}
p = p->fail;
}
if(p == NULL) tmp->next[i]->fail = root;
}
q[head++] = tmp->next[i];
}
}
}
char s[25],str[N];
int dp[N][N];
int main(){
int caser = 0;
int n;
while(~scanf("%d",&n) && n){
tot = 0;
root = new Node();
trie[tot-1] = root;
for(int i=1;i<=n;i++){
scanf(" %s",s);
Insert(s);
}
scanf(" %s",str+1);
Get_Fail();
memset(dp,inf,sizeof(dp));
dp[0][0] = 0;
int len = strlen(str+1);
for(int i=1;i<=len;i++){
for(int j=0;j<tot;j++){ //从结点j出发，所以第i-1分字符必须要能够到达第j个结点
if(dp[i-1][j] == inf) continue;
for(int k=0;k<4;k++){
if(trie[j]->next[k]->cnt) continue; //如果是危险结点
int index = trie[j]->next[k]->index; //第j个结点所能达到的最远的结点。
dp[i][index] = min(dp[i][index],dp[i-1][j] + (k != getnum(str[i]))); //不相同则改变+1
}
}
}
int ans = inf;
for(int i=0;i<tot;i++)
ans = min(ans,dp[len][i]);
printf("Case %d: %d\n",++caser,ans == inf ? -1 : ans);
}
return 0;
}
