Zoj 3494 BCD Code (字符串_AC自动机(数位DP))
题目大意: 问A到B之间的所有整数，转换成BCD Code后，有多少个不包含属于给定病毒串集合的子串,A,B <=10^200,病毒串总长度<= 2000.
解题思路: 因为时间问题，这是我这次复习AC自动机的最后一题了。ac自动机A的很爽，可是其他方面太弱逼，无可奈何必须去复习其他方面了。
看完题目就给出题者跪了，看似毫不相关但实则有联系的的两个东西被结合起来，真是神来之笔。AC自动机上明显的状态使得我们很容易在AC自动机上进行DP，而数位DP又是DP里面一类比较典型的DP，之前我一直认为数位DP应该是利用数字直接一位一位的构造就可以，这题利用自动机构造出一个数字与其他数字间能否相互到达的矩阵，然后利用这个矩阵进行数位DP。这样一分析，似乎并不是毫无相关。
以终为始，我们先分析下最后的数位dp为什么需要用到自动机。如果一个数不含病毒串，那么这个数中的所有数字编成BCD码并且连接起来后就必须不包含病毒串。普通的数位DP构造的两个相邻数字没什么约束，而这题的约束有两个，一是数字本身编成BCD码后可能含有病毒串，二是两个数字连起来后他们的BCD码也连起来了，这时可能含有病毒串，一是二的特例。这样问题就转变成了我们构造若干个串，使得这些串不包含病毒串。问题一转变就和AC自动机扯上关系了，我们用这个串去ac自动机上跑一跑就知道含不含病毒串了。
我们需要将自动机上的状态压缩成一个mat[MAXSIZE][10]矩阵，mat[i][j]表示位置i走过j编成的BCD码即四位二进制数后到达的位置，如果没办法到达设为-1.接着我们利用mat进行数位DP，mat[i][j]中的i表示位置，但除root外它也表示数字，i->next[k] = ii，这里的ii就表示k。
用dp[pos][ac][limit][zero]来表示状态，pos表示数字的第几位，ac为ac自动机上的位置，limit=0表示没有上限，limit=1表示上限为digit[pos],zero为0表示非前导0，此时需要判断mat[ac][k]是否为-1，为-1说明没办法构造下一个数字k，否则可以构造，当zero为1表示是前导0，如果下一个是0那么表示这些都是无用的0，转移到下一个位置都应该是root，不是0的话就需要判断mat[0][k]了。
状态明确了以后用记忆化搜索很好写。
测试数据：
Input:
10
0
1 10
1
00
1 10
1
00
1 100
1
1111
1 100
2
01
10
1 100
Output:
10
3
9
98
0
代码：
[cpp]
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXNODE 2
#define MAXSIZE 2100
#define MOD 1000000009
int n,m;
int ans;
char str[MAXSIZE];
char A[MAXSIZE],B[MAXSIZE];
struct ACnode {
int flag,in;
ACnode *next[MAXNODE],*fail,*father;
};
struct AC_Auto {
int head,tail,total;
int digit[210];
int ans,dp[210][MAXSIZE][2][2];
int next[MAXSIZE][10];
ACnode *root,*p,*q;
ACnode *qu[MAXSIZE],tree[MAXSIZE];
void Initial() {
total = 0;
head = tail = 0;
root = CreateNode();
root->fail = root;
}
ACnode *CreateNode() {
tree[total].flag = 0;
tree[total].in = total;
tree[total].next[0] = NULL;
tree[total].next[1] = NULL;
return &tree[total++];
}
int GetHash(char c) {
return c - '0';
}
void Insert(char *str) {
p = root;
for (int i = 0; str[i]; ++i) {
int k = GetHash(str[i]);
if (p->next[k] == NULL)
p->next[k] = CreateNode();
p = p->next[k];
}
p->flag = 1;
}
void Build_AC() {
qu[head++] = root;
while (tail < head) {
p = qu[tail++];
for (int k = 0; k < MAXNODE; ++k)
if (p->next[k]) {
if (p == root) p->next[k]->fail = root;
else p->next[k]->fail = p->fail->next[k];
p->next[k]->flag |= p->next[k]->fail->flag;
qu[head++] = p->next[k];
}
else {
if (p == root) p->next[k] = root;
else p->next[k] = p->fail->next[k];
}
}
}
int Next(int pos,int num) {
if (tree[pos].flag == 1) return -1;
int realpos = pos;
for (int i = 3; i >= 0; --i) {
int k = ((num >> i) & 1);
if (tree[realpos].next[k]->flag != 1)
realpos = tree[realpos].next[k]->in;
else return -1;
}
补充：软件开发 , C++ ,
