题目大意：

修改文本串的上的字符，使之不出现上面出现的串。问最少修改多少个。

思路分析：

dp[i][j]表示现在 i 个字符改变成了字典树上的 j 节点。

然后顺着自动机一直转移方程。

注意合法与不合法。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define inf 0x3f3f3f3f using namespace std; const char tab = 0; const int max_next = 4; int idx; struct trie { struct trie *fail; struct trie *next[max_next]; int isword; int index; trie() { isword=0; memset(next,NULL,sizeof next); fail=NULL; } }; int rev[256]; trie *que[100005],ac[100005]; int head,tail; trie *New() { trie *temp=&ac[idx]; for(int i=0;i<4;i++)temp->next[i]=NULL; temp->fail=NULL; temp->isword=0; temp->index=idx++; return temp; } void Insert(trie *root,char *word,int len){ trie *t=root; for(int i=0;i
      
       next[rev[word[i]]]==NULL) t->next[rev[word[i]]]=New(); t=t->next[rev[word[i]]]; } t->isword++; } void acbuild(trie *root){ int head=0,tail=0; que[tail++]=root; root->fail=NULL; while(head
       
        next[i]){ if(temp==root)temp->next[i]->fail=root; else { p=temp->fail; while(p!=NULL){ if(p->next[i]){ temp->next[i]->fail=p->next[i]; break; } p=p->fail; } if(p==NULL)temp->next[i]->fail=root; } if(temp->next[i]->fail->isword)temp->next[i]->isword++; que[tail++]=temp->next[i]; } else if(temp==root)temp->next[i]=root; else temp->next[i]=temp->fail->next[i]; } } } void del(trie *root) { for(int i=0;i
        
         next[i])del(root->next[i]); free(root); } int dp[2005][2005]; int solve(char *word,int len) { memset(dp,0x3f,sizeof dp); dp[0][0]=0; for(int i=1;i<=len;i++) { for(int j=0;j
         
          index; if(ac[p].isword)continue; dp[i][p]=min(dp[i][p],dp[i-1][j]+(k!=rev[word[i-1]])); } } } int ans=inf; for(int i=0;i