hdu2457 AC自动机+dp

一、题目

二、思路和代码 1.思路

经典的AC自动机+dp （x2）

dp[i][j]表示考虑前i个字符， 且后缀模式为状态 [root, j] 的最少处理次数

2.读入数据

代码如下：

#include 
#include 
#include 
using namespace std;
const int maxn = 2000;
const int inf = 0x3f3f3f3f;
struct node {
  int next[4];
  int cnt, end;
  void init() {
    memset(next, 0, sizeof(next));
    cnt = 0;
    end = 0;
  }
} trie[maxn];
int cnt, fail[maxn];

int ans;
char str[maxn];
int dp[maxn][maxn];
int n;
void init() {
  cnt = 0, ans = inf;
  memset(fail, 0, sizeof(fail));
  memset(dp, 0x3f, sizeof(dp));
  dp[0][0] = 0;
  trie[0].init();
}
void insert(char *s) {
  int len = strlen(s);
  int u = 0;
  for (int i = 0; i