专题小节之AC自动机

OI 中所说的“自动机”一般都指“确定有限状态自动机”。

而所谓的自动机是一种数学模型，它表现成一张由点和边构成的有向图。

点表示（可接受/存在）状态，边表示转移（条件）。

自动机有一个表示起始状态的点，给出一个输入（可以是字符串），然后从起始点出发，根据边的转移条件，转移到下一个点，不断这样在不同状态转移，最终到达了某一个状态。

这过程就像是一个会自动工作的机器一样，确定了状态和转移条件，只要给它一个输入，它就能按照既定的条件去工作，直至停止。

推荐阅读OI Wiki-AC automation

AC自动机

AC自动机的功能

AC自动机能够实现多模板串的匹配操作。

它结合了(Trie)树的结构和(KMP)的思想，

• 根据模板串构建一棵(Trie)树。
• 在(Trie)树的各个节点上构建失配指针(fail)指针。

在这里，每个点表示一个状态，即某个模板串的某个前缀。每条边表示转移条件，即接下来的字母是什么。

而失配指针是指向与当前状态所代表的字符串的最长前后缀对应的字符串的节点，它跟KMP里的(next)数组类似，它用于辅助构造其他转移的边，表示当前状态没有后继状态（点）的时候，该去哪个已有状态（点）。

(fail)指针和(next)数组的相同之处，就是指向的是当前字符串前缀的最长前后缀的字符串状态。

而不同之处在于，(next)所指向的都是同一个字符串的前缀，而(fail)链指向的可能是另一个字符串的前缀。

AC自动机包含了转移函数(trans[cur][i])，表示当前状态为(cur),接下来的字母（转移条件）是(i)，所对应的状态。

还有一个(fail)指针。

如何构建fail指针

AC自动机里，节点的深度就是该状态所代表的字符串的长度。

(fail)指针指向的是该字符串的最长前后缀的节点，其深度一定不大于原来的节点的深度。

所以我们需要从深度小的节点开始构造，于是用到(BFS)。

假设当前节点为(cur)，其父亲节点是(fa),通过字符(c)连接到了(cur)，即(trans[fa][c] = cur)，所有深度小于(cur)的(fail)指针已经构造完毕了。

• 如果(trans[fail[fa]][c])存在，那么(fail[cur] = trans[fail[fa]][c])
• 如果(trans[fail[fa]][c])不存在，那么我们再找(trans[fail[fail[fa]]][c])，(trans[fail[fail[fail[fa]]]][c]......)，直到存在或者回到了根节点，将存在的那个点或者根节点赋给(fail[cur])。

如何拿AC自动机去匹配

设当前状态是(cur)，接下来的字母（转移条件）是(i)

• 如果(trans[cur][i])存在，那么(cur = trans[cur][i])
• 如果(trans[cur][i])不存在，那么不断(cur = fail[cur])，直到(trans[cur][i])存在，令(cur = trans[cur][i])

注意到当如果(trans[cur][i])不存在，我们是要不断跳fail指针跳到一个存在的节点，那么我们可以一开始就将这个不存在的trans[cur][i]值赋为那个节点，这样我们就可以不跳fail指针，即将这两个节点连一条边，能够一步转移到那个点，从而减少跳fail指针的次数。

模板

AC自动机

#include <bits/stdc++.h>

class AC_automation
{
#define tot_solution 1000000
#define tot_mark 26

    int trans[tot_solution][tot_mark]; //转移函数
    int fail[tot_solution];            //fail指针
    int last[tot_solution];            //加强版fail指针，每次跳到是结尾字符的地方
    int cnt[tot_solution];             //当前状态对应的字符串数量
    int id[tot_solution];              //当前状态对应的字符串编号
    int tot;                           //总状态数
    int num;                           //字符串总数

public:
    void clear()
    {
        for (int i = 0; i <= tot; ++i)
        {
            fail[i] = last[i] = cnt[i] = id[i] = 0;
            for (int j = 0; j < tot_mark; ++j)
            {
                trans[i][j] = 0;
            }
        }
        tot = num = 0;
    }

    void insert(const char *s, int index)
    {
        int cur = 0;
        for (size_t i = 0; s[i]; ++i)
        {
            if (!trans[cur][s[i] - 'a'])
                trans[cur][s[i] - 'a'] = ++tot;
            cur = trans[cur][s[i] - 'a'];
        }
        ++cnt[cur];
        id[cur] = index;
        ++num;
    }

    void build_fail()
    {
        std::queue<int> team;
        for (int i = 0; i < tot_mark; ++i)
        {
            if (trans[0][i])
                team.push(trans[0][i]);
        }
        int u = 0;
        while (!team.empty())
        {
            u = team.front();
            team.pop();
            for (int i = 0; i < tot_mark; ++i)
            {
                if (trans[u][i])
                {
                    fail[trans[u][i]] = trans[fail[u]][i];
                    last[trans[u][i]] = cnt[fail[trans[u][i]]] ? fail[trans[u][i]] : last[fail[trans[u][i]]];
                    team.push(trans[u][i]);
                }
                else
                {
                    trans[u][i] = trans[fail[u]][i];
                }
            }
        }
    }

    int query(const char *s)
    {
        int ans = 0;
        int cur = 0;
        for (int i = 0; s[i]; ++i)
        {
            cur = trans[cur][s[i] - 'a'];
            for (int j = cur; j && cnt[j] != -1; j = last[j]) //一个小优化
            {
                ans += cnt[j];
                cnt[j] = -1;
            }
        }
        return ans;
    }
};

last优化

在统计答案的时候，我们需要不断跳fail指针，但只有跳到那些代表某个字符串全部的节点，才会对答案有贡献，所以我们就设想能不能直接一步跳到那些代表整个字符串的节点，而不经过那些代表某个字符串前缀的节点。

当然是可以的。

(last[cur])表示从当前节点cur，不断跳(fail)指针，第一个遇到的代表某个字符串的节点，要求出它也很简单。

• 如果(fail[cur])是代表某个字符串的节点，那么(last[cur] = fail[cur])。
• 如果(fail[cur])是代表某个字符串前缀的节点，那么(last[cur] = last[fail[cur]])。

练习题目

自动机是个数学模型，依此很多算法就可以在上面跑，最著名的便是AC自动机fail树DFS序上建可持久化线段树

Keywords Search (HDU 2222)

模板题

---

病毒侵袭 (HDU 2896)

模板+记录匹配的字符串编号即可。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x) {
    int s = 0, c = getchar();
    x = 0;
    while (isspace(c)) c = getchar();
    if (c == 45) s = 1, c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    if (s) x = -x;
}

template <typename T>
void write(T x, char c = ' ') {
    int b[40], l = 0;
    if (x < 0) putchar(45), x = -x;
    while (x > 0) b[l++] = x % 10, x /= 10;
    if (!l) putchar(48);
    while (l) putchar(b[--l] | 48);
    putchar(c);
}

class AC_automation{
    #define N 200000
    #define M 130

    int trans[N][M];
    int fail[N];
    int last[N];
    int cnt[N];
    int id[N];
    int ti[N];
    int tot;
    int num;

    public:

    void insert(const char *s){
        int cur = 0;
        for(size_t i = 0; s[i]; ++ i){
            if (!trans[cur][s[i]]) trans[cur][s[i]] = ++ tot;
            cur = trans[cur][s[i]];
        }
        ++ cnt[cur];
        id[cur] = ++ num;
    }

    void build(){
        queue<int> team;
        for(size_t i = 1; i < M; ++ i){
            if (trans[0][i]) team.push(trans[0][i]);
        }
        int u = 0;
        while(!team.empty()){
            u  = team.front();
            team.pop();
            for(size_t i = 1; i < M; ++ i){
                if (trans[u][i]){
                    fail[trans[u][i]] = trans[fail[u]][i];
                    last[trans[u][i]] = cnt[fail[trans[u][i]]]? fail[trans[u][i]]: last[trans[u][i]];
                    team.push(trans[u][i]);
                }else{
                    trans[u][i] = trans[fail[u]][i];
                }
            }
        }
    }

    int query(const char *s, int vir[],int tt){
        int ans = 0;
        int cur = 0;
        for(size_t i = 0; s[i]; ++ i){
            cur = trans[cur][s[i]];
            for(size_t j = cur; j && ti[j] != tt; j = last[j]){
                if (id[j]){
                    vir[ans++] = id[j];
                    ti[j] = tt;
                }
            }
        }
        return ans;
    }
}AC;

char s[50000];

int num[6];

int main(void) {
    int n;
    read(n);
    for(int i = 1; i <= n; ++ i){
        scanf("%s",s);
        AC.insert(s);
    }
    AC.build();
    int ans = 0;
    read(n);
    int cnt = 0;
    for(int i = 1;i <= n; ++ i){
        scanf("%s",s);
        cnt = AC.query(s, num, i);
        if (cnt){
            ++ ans;
            sort(num,num+cnt);
            printf("web %d:",i);
            for(int j = 0; j < cnt; ++ j){
                printf(" %d",num[j]);
            }
            puts("");
        }
    }
    printf("total: %d
",ans);
    return 0;
}

---

病毒侵袭持续中 (HDU 3065)

模板+统计匹配过程中匹配到的各个模板串的次数即可。

注意网站源码包括空格。

注意多组数据

神奇的代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x) {
    int s = 0, c = getchar();
    x = 0;
    while (isspace(c)) c = getchar();
    if (c == 45) s = 1, c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    if (s) x = -x;
}

template <typename T>
void write(T x, char c = ' ') {
    int b[40], l = 0;
    if (x < 0) putchar(45), x = -x;
    while (x > 0) b[l++] = x % 10, x /= 10;
    if (!l) putchar(48);
    while (l) putchar(b[--l] | 48);
    putchar(c);
}

int cnt[1006];

class AC_automation{
    #define N 200006
    #define M 130

    int trans[N][M];
    int fail[N];
    int last[N];
    int cnt[N];
    int id[N];
    int tot;
    int num;

    public:

    void clear(){
        for(int i = 0; i <= tot; ++ i){
            fail[i] = last[i] = cnt[i] = id[i] = 0;
            for(int j = 0; j < M; ++ j){
                trans[i][j] = 0;
            }
        }
        tot = num = 0;
    }

    void insert(const char *s){
        int cur = 0;
        for(size_t i = 0; s[i]; ++ i){
            if (!trans[cur][s[i]]) trans[cur][s[i]] = ++ tot;
            cur = trans[cur][s[i]];
        }
        ++ cnt[cur];
        id[cur] = ++ num;
    }

    void build(){
        queue<int> team;
        for(size_t i = 1; i < M; ++ i){
            if (trans[0][i]) team.push(trans[0][i]);
        }
        int u = 0;
        while(!team.empty()){
            u  = team.front();
            team.pop();
            for(size_t i = 1; i < M; ++ i){
                if (trans[u][i]){
                    fail[trans[u][i]] = trans[fail[u]][i];
                    last[trans[u][i]] = cnt[fail[trans[u][i]]]? fail[trans[u][i]]: last[fail[trans[u][i]]];
                    team.push(trans[u][i]);
                }else{
                    trans[u][i] = trans[fail[u]][i];
                }
            }
        }
    }

    void query(const char *s,int cc[]){
        int cur = 0;
        for(size_t i = 0; s[i]; ++ i){
            cur = trans[cur][s[i]];
            for(size_t j = cur; j; j = last[j]){
                if (id[j]){
                    cc[id[j]] ++;
                }
            }
        }
    }
}AC;

char s[1001][55];

char ss[2000006];

int main(void) {
    int n;
    while(cin>>n){
    for(int i = 1; i <= n; ++ i){
        scanf("%s",s[i]);
        AC.insert(s[i]);
    }
    AC.build();
    getchar();
    scanf("%[^
]",ss);
    AC.query(ss, cnt);
    for(int i = 1; i <= n; ++i){
        if (cnt[i]) printf("%s: %d
",s[i],cnt[i]);
        cnt[i] = 0;
    }
    AC.clear();
    }
    return 0;
}

---

DNA Sequence (POJ 2778)

题目大意

求指定长度的且不包括指定DNA序列的DNA数量。

解题思路

先根据指定DNA序列构造AC自动机，并将代表那些DNA序列的点视为危险，我们设想有一个DNA拿到自动机上跑，题目的要求便是我们不能抵达危险的点。

假设我们要构造的长度为(l)，由于DNA不同，在自动机上跑的节点就不一样。

于是题目就转化成，从起点出发，不经过危险点的前提下，长度为(l)的路径数是多少。

这便是路径数量统计问题，我们构造矩阵(matrix[i][j])，表示节点(i)直接到节点(j)的路径条数（即有向边的起始点是(i)，终止点是(j)，不是(fail)指针），然后把危险点的行和列都去掉，这样我们就能统计不经过危险点的路径数量。用矩阵快速幂计算这个矩阵的(l)次幂，取首行的和即是答案。

注意危险是可以传递的，即如果一个点(cur)的(fail[cur])是危险的，那么这个点也是危险的。

每次POJ不能写万能头文件不能auto不能双pair的>>连写（小声BB

神奇的代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cmath>

using namespace std;
typedef long long LL;

template <typename T>
void read(T &x) {
    int s = 0, c = getchar();
    x = 0;
    while (isspace(c)) c = getchar();
    if (c == 45) s = 1, c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    if (s) x = -x;
}

template <typename T>
void write(T x, char c = ' ') {
    int b[40], l = 0;
    if (x < 0) putchar(45), x = -x;
    while (x > 0) b[l++] = x % 10, x /= 10;
    if (!l) putchar(48);
    while (l) putchar(b[--l] | 48);
    putchar(c);
}

class AC_automation{
    #define N 105
    #define M 4

    int trans[N][M];
    int fail[N];
    int sign[N];
    int tot;

    public:
    void insert(const char *s){
        int cur = 0;
        sign[cur] = 0;
        for(int i = 0; s[i]; ++ i){
            if (! trans[cur][s[i] - '0']){
                trans[cur][s[i] - '0'] = ++ tot;
                sign[tot] = 0;
            }
            cur = trans[cur][s[i] - '0'];
        }
        sign[cur] = 1;
    }

    void build(){
        queue<int> team;
        for(int i = 0; i < M; ++ i){
            if (trans[0][i]) team.push(trans[0][i]);
        }
        int u = 0;
        while(! team.empty()){
            u = team.front();
            team.pop();
            for(int j = 0; j < M; ++ j){
                if (trans[u][j]){
                    fail[trans[u][j]] = trans[fail[u]][j];
                    team.push(trans[u][j]);
                }else{
                    trans[u][j] = trans[fail[u]][j];
                }
                sign[trans[u][j]] |= sign[fail[trans[u][j]]];
            }
        }
    }

    friend LL work(LL);
}AC;

const LL mo = 100000;

class Matrix{
    public:
    LL a[106][106];
    int n;

    Matrix(int ss,int val = 0){
        n=ss;
        for(int i = 0; i < n; ++ i)
            for(int j = 0; j < n; ++ j){
                a[i][j] = val;
            }
    }

    Matrix(const Matrix & b){
        n = b.n;
        for(int i = 0; i < n; ++ i){
            for(int j = 0; j < n; ++ j){
                a[i][j] = b.a[i][j];
            }
        }
    }

    Matrix operator * (const Matrix & b){
        Matrix tmp(this->n);
        for(int i = 0; i < n; ++ i)
            for(int j = 0; j < n; ++ j)
                for(int k = 0; k < n; ++ k)
                    tmp.a[i][j] = (a[i][k] * b.a[k][j] % mo + tmp.a[i][j]) % mo;
        return tmp;
    }

    void print(){
        for(int i = 0; i < n ; ++ i){
            for(int j = 0; j < n; ++ j){
                printf("%lld%c",a[i][j],j==n-1?'
':' ');
            }
        }
    }
};

Matrix qpower(Matrix a, LL b){
    Matrix tmp(a.n);
    for(int i = 0; i < a.n; ++ i)
        tmp.a[i][i] = 1;
    while(b){
        if (b&1) tmp = tmp * a;
        a = a * a;
        b >>= 1;
    }
    return tmp;
}

LL work(LL n){
    int cnt = AC.tot;
    Matrix ma(cnt+1);
    for(int i = 0; i <= cnt; ++ i){
        for(int j = 0; j < M; ++ j){
            ++ ma.a[i][AC.trans[i][j]];
        }
    }
    int qaq = 0;
    for(int i = 0; i <= cnt; ++ i){
        if (! AC.sign[i]) ++ qaq;
    }
    Matrix tmp(qaq);
    int x = -1, y = 0;
    for(int i = 0; i <= cnt; ++ i){
        if (AC.sign[i]) continue;
        y = 0;
        ++ x;
        for (int j = 0; j <= cnt; ++ j){
            if (AC.sign[j]) continue;
            tmp.a[x][y] = ma.a[i][j];
            ++ y;
        }
    }
    // tmp.print();
    Matrix qwq = qpower(tmp,n);
    LL ans = 0;
    for(int i = 0; i < qaq; ++ i)
        ans = (ans + qwq.a[0][i]) % mo;
    return ans;
}

char s[15];

int main(){
    int m;
    LL n;
    read(m);
    read(n);
    while(m--){
        scanf("%s",s);
        for(size_t i = 0; s[i]; ++ i){
            switch(s[i]){
                case 'A' : s[i] = '0'; break;
                case 'C' : s[i] = '1'; break;
                case 'T' : s[i] = '2'; break;
                case 'G' : s[i] = '3'; break;
            }
        }
        AC.insert(s);
    }
    AC.build();
    LL ans;
    ans = work(n);
    write(ans,'
');
    return 0;
}

---

考研路茫茫——单词情结 (HDU 2243)

题目大意

给定几个单词，问长度不超过(l)的，至少包含一个给定单词的，单词数。

解题思路

考虑逆向，计算不包括单词的单词数量，即上题的危险节点。

同样构造矩阵(A)，但不同之处在于这里要求(A,A^1,A^2,...,A^n)的第一行的累加和。

于是我们再构造矩阵

[left[ egin{matrix} A & E \ 0 & E \ end{matrix} ight] ]

计算它的(l)次方后第一行的和减一则是答案。

然后再计算(26+26^1+26^2+...+26^l)同样构造矩阵计算

[left[ egin{matrix} 26 & 1 \ 0 & 1 \ end{matrix} ight] ]

这样就不用等比和求逆，
其(l)次方的第一行和减一则是和，两个和相减即是答案。

神奇的代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

template <typename T>
void read(T &x) {
    int s = 0, c = getchar();
    x = 0;
    while (isspace(c)) c = getchar();
    if (c == 45) s = 1, c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    if (s) x = -x;
}

template <typename T>
void write(T x, char c = ' ') {
    int b[40], l = 0;
    if (x < 0) putchar(45), x = -x;
    while (x > 0) b[l++] = x % 10, x /= 10;
    if (!l) putchar(48);
    while (l) putchar(b[--l] | 48);
    putchar(c);
}

class AC_automation{
    #define N 40
    #define M 26

    int trans[N][M];
    int fail[N];
    int sign[N];
    int tot;

    public:
    void insert(const char *s){
        int cur = 0;
        sign[cur] = 0;
        for(int i = 0; s[i]; ++ i){
            if (! trans[cur][s[i] - 'a']){
                trans[cur][s[i] - 'a'] = ++ tot;
                sign[tot] = 0;
            }
            cur = trans[cur][s[i] - 'a'];
        }
        sign[cur] = 1;
    }

    void build(){
        queue<int> team;
        for(int i = 0; i < M; ++ i){
            if (trans[0][i]) team.push(trans[0][i]);
        }
        int u = 0;
        while(! team.empty()){
            u = team.front();
            team.pop();
            for(int j = 0; j < M; ++ j){
                if (trans[u][j]){
                    fail[trans[u][j]] = trans[fail[u]][j];
                    team.push(trans[u][j]);
                }else{
                    trans[u][j] = trans[fail[u]][j];
                }
                sign[trans[u][j]] |= sign[fail[trans[u][j]]];
            }
        }
    }

    void init(){
        for(int i = 0; i <= tot; ++ i){
            sign[i] = fail[i] = 0;
            for(int j = 0; j < M; ++ j){
                trans[i][j] = 0;
            }
        }
        tot = 0;
    }

    friend unsigned long long work(LL);
}AC;

class Matrix{
    public:
    unsigned long long a[106][106];
    int n;

    Matrix(int ss,unsigned long long val = 0){
        n=ss;
        for(int i = 0; i < 106; ++ i)
            for(int j = 0; j < 106; ++ j){
                a[i][j] = val;
            }
    }

    Matrix(const Matrix & b){
        n = b.n;
        for(int i = 0; i < n; ++ i){
            for(int j = 0; j < n; ++ j){
                a[i][j] = b.a[i][j];
            }
        }
    }

    Matrix operator * (const Matrix & b){
        Matrix tmp(this->n);
        for(int i = 0; i < n; ++ i)
            for(int j = 0; j < n; ++ j)
                for(int k = 0; k < n; ++ k)
                    tmp.a[i][j] = (a[i][k] * b.a[k][j] + tmp.a[i][j]);
        return tmp;
    }

    void print(){
        for(int i = 0; i < n ; ++ i){
            for(int j = 0; j < n; ++ j){
                printf("%llu%c",a[i][j],j==n-1?'
':' ');
            }
        }
    }
};

Matrix qpower(Matrix a, LL b){
    Matrix tmp(a.n);
    for(int i = 0; i < a.n; ++ i)
        tmp.a[i][i] = 1;
    while(b){
        if (b&1) tmp = tmp * a;
        a = a * a;
        b >>= 1;
    }
    return tmp;
}

unsigned long long work(LL n){
    int cnt = AC.tot;
    Matrix ma(cnt+1);
    for(int i = 0; i <= cnt; ++ i){
        for(int j = 0; j < M; ++ j){
            ++ ma.a[i][AC.trans[i][j]];
        }
    }
    int qaq = 0;
    for(int i = 0; i <= cnt; ++ i){
        if (! AC.sign[i]) ++ qaq;
    }
    Matrix tmp(qaq);
    int x = -1, y = 0;
    for(int i = 0; i <= cnt; ++ i){
        if (AC.sign[i]) continue;
        y = 0;
        ++ x;
        for (int j = 0; j <= cnt; ++ j){
            if (AC.sign[j]) continue;
            tmp.a[x][y] = ma.a[i][j];
            ++ y;
        }
    }
    // tmp.print();
    for(int i = tmp.n; i < 2 * tmp.n; ++ i){
        tmp.a[i-tmp.n][i] = 1;
        tmp.a[i][i] = 1;
    }
    tmp.n *= 2;
    // tmp.print();
    Matrix qwq = qpower(tmp,n+1);
    unsigned long long ans = 0;
    for(int i = qwq.n / 2; i < qwq.n; ++ i)
        ans = (ans + qwq.a[0][i]);
    Matrix tot_ans(2);
    tot_ans.a[0][0]=26;
    tot_ans.a[0][1]=1;
    tot_ans.a[1][1]=1;
    tot_ans = qpower(tot_ans,n+1);
    ans = tot_ans.a[0][1] - ans;
    return ans;
}

char s[15];

int main(){
    int m;
    LL n;
    while(~scanf("%d%lld
",&m,&n)){
        while(m--){
            scanf("%s",s);
            AC.insert(s);
        }
        AC.build();
        unsigned long long ans;
        ans = work(n);
        printf("%llu
",ans);
        AC.init();
    }
    return 0;
}

---

DNA repair (HDU 2457)

题目大意

给定若干个DNA序列和一个很长的DNA，要求对DNA的某些字符进行替换，使得DNA不包含任何给定的DNA序列，问最小的替换次数。

解题思路

最优化问题，从爆搜的角度很容易考虑到记忆化即(DP)

(dp[i][j])表示DNA前(i)个字符中不含给定的DNA序列，当前所在状态为(j)的最小替换次数，枚举下一个字符，与原DNA中第(i+1)个字符相等则直接转移，不相等则加一，表示执行了一次替换操作。

给定的DNA序列即为危险节点，转移时不能经过它们。

注意危险是可以传递的，即如果一个点(cur)的(fail[cur])是危险的，那么这个点也是危险的。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <typename T>
void read(T &x) {
    int s = 0, c = getchar();
    x = 0;
    while (isspace(c)) c = getchar();
    if (c == 45) s = 1, c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    if (s) x = -x;
}

template <typename T>
void write(T x, char c = ' ') {
    int b[40], l = 0;
    if (x < 0) putchar(45), x = -x;
    while (x > 0) b[l++] = x % 10, x /= 10;
    if (!l) putchar(48);
    while (l) putchar(b[--l] | 48);
    putchar(c);
}

class AC_automation{
    #define N 1005
    #define M 4

    int trans[N][M];
    int fail[N];
    int sign[N];
    int alp[N];
    int tot;
    int len;
    int dp[N][N];

    public:

    void insert(const char *s){
        int cur = 0;
        sign[cur] = 0;
        for(size_t i = 0; s[i]; ++ i){
            if (! trans[cur][s[i] - '0']){
                trans[cur][s[i] - '0'] = ++ tot;
                sign[tot] = 0;
                alp[tot] = s[i] - '0';
            }
            cur = trans[cur][s[i] - '0'];
        }
        sign[cur] = 1;
    }

    void build(){
        queue<int> team;
        for(int i = 0; i < M; ++ i){
            if (trans[0][i]) team.push(trans[0][i]);
        }
        int u = 0;
        while(! team.empty()){
            u = team.front();
            team.pop();
            for(int i = 0; i < M; ++ i){
                if (trans[u][i]){
                    fail[trans[u][i]] = trans[fail[u]][i];
                    sign[trans[u][i]] |= sign[fail[trans[u][i]]];
                    team.push(trans[u][i]);
                }else{
                    trans[u][i] = trans[fail[u]][i];
                }
            }
        }
    }

    void init(){
        for(int i = 0; i <= tot; ++ i){
            fail[i] = sign[i] = alp[i] = 0;
            for(int j = 0; j < M; ++ j)
                trans[i][j] = 0;
        }
        tot = 0;
    }

    int get_ans(const char* s){
        len = strlen(s);
        for(int i = 0; i <= len; ++ i){
            for(int j = 0; j <= tot; ++ j)
                dp[i][j] = 1024;
        }
        dp[0][0] = 0;
        for(size_t i = 1; s[i-1]; ++ i){
            for(int j = 0; j <= tot; ++ j)
            for(int k = 0; k < M; ++ k){ 
                if (sign[trans[j][k]]) continue;
                if (dp[i-1][j] == 1024) continue;
                dp[i][trans[j][k]] = min(dp[i][trans[j][k]],dp[i-1][j]+(k != (s[i-1]-'0')));
            }
        }
        int ans = 1024;
        for(int i = 0; i <= tot; ++ i){
            ans = min(ans, dp[len][i]);
        }
        return ans==1024?-1:ans;
    }
}AC;

char s[1005];

void change(char *s){
    for(size_t i = 0; s[i]; ++ i){
        switch(s[i]){
            case 'A': s[i] = '0'; break;
            case 'C': s[i] = '1'; break;
            case 'T': s[i] = '2'; break;
            case 'G': s[i] = '3'; break;
        }
    }
}

int main(){
    int n;
    int ans;
    int t=0;
    while(true){
        ++t;
        read(n);
        if (n == 0) break;
        while(n--){
            scanf("%s",s);
            change(s);
            AC.insert(s);
        }
        AC.build();
        scanf("%s",s);
        change(s);
        ans = AC.get_ans(s);
        printf("Case %d: %d
",t,ans);
        AC.init();
    }
    return 0;
}

---

Ring (HDU 2296)

题目大意

给定几个字符串以及它们的价值，要求构造一个长度不超过(N)的字符串，它的价值最大。输出这个字符串，价值相同取长度最短，长度相同取字典序最小。

字符串的价值就是给定的字符串的出现次数乘以对应的价值的和。

答案可能是空串。

解题思路

最优化问题，设(dp[i][j])表示当前长度为(i)，在第(j)个节点状态的最大价值，由于字典序最小，从初始点SPFA式DP。

同时用(s[i][j])记录当前dp数组所表示的字符串。

注意一个节点状态的价值具有传递性，即如果(fail[cur])的状态具有相应价值，那么(cur)的状态也具有相应价值。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <typename T>
void read(T &x) {
    int s = 0, c = getchar();
    x = 0;
    while (isspace(c)) c = getchar();
    if (c == 45) s = 1, c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    if (s) x = -x;
}

template <typename T>
void write(T x, char c = ' ') {
    int b[40], l = 0;
    if (x < 0) putchar(45), x = -x;
    while (x > 0) b[l++] = x % 10, x /= 10;
    if (!l) putchar(48);
    while (l) putchar(b[--l] | 48);
    putchar(c);
}

class AC_automation{
    #define N 1120
    #define M 26

    int trans[N][M];
    int fail[N];
    int last[N];
    int id[105];
    int cost[N];
    int dp[M*2][N];
    bool visit[M*2][N];
    string alp[N];
    string s[M*2][N];
    int tot;
    int num;

    public:

    void init(){
        for(int i = 0; i <= tot; ++ i){
            fail[i] = last[i] = id[i] = 0;
            alp[i].clear();
            for(int j = 0; j < M; ++ j){
                trans[i][j] = 0;
            }
        }
        for(int i = 0; i <= tot; ++ i)
            cost[i] = 0;
        tot = 0;
        num = 0;
    }

    void insert(const char *s){
        int cur = 0;
        for(size_t i = 0; s[i]; ++ i){
            if (! trans[cur][s[i] - 'a']){
                trans[cur][s[i] - 'a'] = ++ tot;
                alp[tot] = s[i];
            }
            cur = trans[cur][s[i] - 'a'];
        }
        ++ num;
        id[num] = cur;
    }

    void read_cval(int m){
        for(int i = 1; i <= m; ++ i){
            read(cost[id[i]]);
        }
    }

    void build(){
        queue<int> team;    
        for(int i = 0; i < M; ++ i){
            if (trans[0][i]) team.push(trans[0][i]);
        }
        int u = 0;
        while(! team.empty()){
            u = team.front();
            team.pop();
            for(int i = 0; i < M; ++ i){
                if (trans[u][i]){
                    fail[trans[u][i]] = trans[fail[u]][i];
                    last[trans[u][i]] = id[fail[trans[u][i]]]? fail[trans[u][i]]: last[fail[trans[u][i]]];
                    cost[trans[u][i]] += cost[fail[trans[u][i]]];
                    team.push(trans[u][i]);
                }
                else{
                    trans[u][i] = trans[fail[u]][i];
                }
            }
        }
    }

    string get_ans(int len){
        for(int i = 0; i <= len; ++ i){
            for(int j = 0; j <= tot; ++ j){
                dp[i][j] = -1;
                visit[i][j] = 0;
                s[i][j].clear();
            }
        }
        dp[0][0] = 0;
        visit[0][0] = 1;
        queue<pair<int,int>> team;
        team.push(make_pair(0,0));
        while(! team.empty()){
            auto u = team.front();
            team.pop();
            visit[u.first][u.second] = false;
            if (u.first == len) continue;
            for(int i = 0; i < M; ++ i){
                auto v = u;
                v.first = u.first + 1;
                v.second = trans[u.second][i];
                if (v.second == 0) continue;
                if (dp[v.first][v.second] == -1){
                    dp[v.first][v.second] = dp[u.first][u.second] + cost[v.second];
                    s[v.first][v.second] = s[u.first][u.second] + alp[v.second];
                    if (!visit[v.first][v.second]){
                        team.push(v);
                        visit[v.first][v.second] = true;
                    }
                }else if (dp[v.first][v.second] <= dp[u.first][u.second] + cost[v.second]){
                    if (dp[v.first][v.second] < dp[u.first][u.second] +cost[v.second]){
                       dp[v.first][v.second] = dp[u.first][u.second] +cost[v.second];
                       s[v.first][v.second] = s[u.first][u.second] + alp[v.second];
                    }else{
                        string qwq = s[u.first][u.second] + alp[v.second];
                        if (qwq < s[v.first][v.second]) s[v.first][v.second] = qwq;
                    }
                    if (!visit[v.first][v.second]){
                        team.push(v);
                        visit[v.first][v.second] = true;
                    }
                }
            }
        }
        string ans;
        ans.clear();
        int aval = -1;
        for(int i = 0; i <= tot; ++ i)
            for(int j = 0; j <= len; ++ j){
                if (dp[j][i] != -1){
                    if (aval < dp[j][i]){
                        aval = dp[j][i];
                        ans = s[j][i];
                    }else if (aval == dp[j][i] && s[j][i].size() < ans.size()){
                        ans = s[j][i];
                    }else if (aval == dp[j][i] && s[j][i].size() == ans.size() && s[j][i] < ans){
                        ans = s[j][i];
                    }
                }
            }
        return ans;
    }
}AC;

char s[12];

string ans;

int main(){
    int t;
    read(t);
    while(t--){
        int n;
        read(n);
        int m;
        read(m);
        for(int i = 0; i < m; ++ i){
            scanf("%s",s);
            AC.insert(s);
        }
        AC.read_cval(m);
        AC.build();
        ans = AC.get_ans(n);
        printf("%s
",ans.c_str());
        AC.init();
    }
    return 0;
}

---

Lost's revenge (HDU 3341)

题目大意

给定若干个DNA序列以及一个DNA，要求对DNA进行重新排序，使得重新排序后的DNA包含尽可能的多个给定的DNA序列，问最大数量。

如果一个DNA序列出现多次则计算多次。

解题思路

最优化问题，与前面的问题不同的是当前可转移的取决于还有多少个(ACGT)没用

考虑(dp[i][j])表示当前在第(i)个节点的状态，可以使用的(ACGT)的数量(hash)值为(j)的答案，枚举下一个转移条件即可,SPFA式DP。

因为(40^4)会MLE所以需要(hash)状态。

假设初始有(a,b,c,d)个(ACGT)可以选，当前有(A,C,G,T)个(ACGT)可选，则(hash(A,C,G,T) = A imes (a+1) imes (b+1) imes (c+1) + C imes (b+1) imes (c+1) + G imes (c+1) + T)。

由均值不等式得(hash(A,C,G,T))的最大值为(11^4 = 14641)

神奇的代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <typename T>
void read(T &x) {
    int s = 0, c = getchar();
    x = 0;
    while (isspace(c)) c = getchar();
    if (c == 45) s = 1, c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    if (s) x = -x;
}

template <typename T>
void write(T x, char c = ' ') {
    int b[40], l = 0;
    if (x < 0) putchar(45), x = -x;
    while (x > 0) b[l++] = x % 10, x /= 10;
    if (!l) putchar(48);
    while (l) putchar(b[--l] | 48);
    putchar(c);
}

class AC_automation{
    #define N 508
    #define M 4

    int trans[N][M];
    int fail[N];
    int cost[N];
    int dp[N][14646];
    bool visit[N][14646];
    int tot;

    public:

    void init(){
        for(int i = 0; i <= tot; ++ i){
            fail[i] = 0;
            for(int j = 0; j < M; ++ j){
                trans[i][j] = 0;
            }
        }
        for(int i = 0; i <= tot; ++ i)
            cost[i] = 0;
        tot = 0;
    }

    void insert(const char *s){
        int cur = 0;
        for(size_t i = 0; s[i]; ++ i){
            if (! trans[cur][s[i] - '0']){
                trans[cur][s[i] - '0'] = ++ tot;
            }
            cur = trans[cur][s[i] - '0'];
        }
        ++ cost[cur];
    }


    void build(){
        queue<int> team;    
        for(int i = 0; i < M; ++ i){
            if (trans[0][i]) team.push(trans[0][i]);
        }
        int u = 0;
        while(! team.empty()){
            u = team.front();
            team.pop();
            for(int i = 0; i < M; ++ i){
                if (trans[u][i]){
                    fail[trans[u][i]] = trans[fail[u]][i];
                    cost[trans[u][i]] += cost[fail[trans[u][i]]];
                    team.push(trans[u][i]);
                }
                else{
                    trans[u][i] = trans[fail[u]][i];
                }
            }
        }
    }

#define hash(a,b,c,d) (a)*(cnt[1]+1)*(cnt[2]+1)*(cnt[3]+1)+(b)*(cnt[2]+1)*(cnt[3]+1)+(c)*(cnt[3]+1)+(d)

    int get_ans(const char * s){
        int cnt[4] = {0};
        for(size_t i = 0; s[i]; ++ i){
            ++ cnt[s[i] - '0'];
        }
        for(int i = 0; i <= tot; ++ i)
            for(int j = 0; j <= hash(cnt[0],cnt[1],cnt[2],cnt[3]); ++ j){
                dp[i][j] = -1;
                visit[i][j] = 0;
            }
        dp[0][hash(cnt[0],cnt[1],cnt[2],cnt[3])] = 0;
        visit[0][hash(cnt[0],cnt[1],cnt[2],cnt[3])] = 1;
        queue<pair<int,int>> team;
        team.push(make_pair(0,hash(cnt[0],cnt[1],cnt[2],cnt[3])));
        int c[4] = {0};
        while(! team.empty()){
            auto u = team.front();
            team.pop();
            visit[u.first][u.second] = false;
            c[3] = u.second % (cnt[3] + 1);
            c[2] = u.second % ((cnt[3] + 1) * (cnt[2] + 1)) - c[3];
            c[1] = u.second % ((cnt[3] + 1) * (cnt[2] + 1) * (cnt[1] + 1)) - c[2] - c[3];
            c[0] = u.second - c[1] - c[2] - c[3];
            c[2] /= (cnt[3] + 1);
            c[1] /= (cnt[3] + 1) * (cnt[2] + 1);
            c[0] /= (cnt[3] + 1) * (cnt[2] + 1) * (cnt[1] + 1);
            for(int i = 0; i < M; ++ i){
                if (c[i] == 0) continue;
                auto v = u;
                v.first = trans[u.first][i];
                v.second = hash(c[0] - (i == 0), c[1] - (i == 1), c[2] - (i == 2), c[3] - (i == 3));
                if (dp[v.first][v.second] < dp[u.first][u.second] + cost[v.first]){
                       dp[v.first][v.second] = dp[u.first][u.second] + cost[v.first];
                    if (!visit[v.first][v.second]){
                        team.push(v);
                        visit[v.first][v.second] = true;
                    }
                }
            }
        }
        int aval = -1;
        for(int i = 0; i <= tot; ++ i){
                aval = max(aval, dp[i][0]);
        }
        return aval;
    }
}AC;

char s[46];

void change(char *s){
    for(size_t i = 0; s[i]; ++ i){
        switch(s[i]){
            case 'A': s[i] = '0'; break;
            case 'C': s[i] = '1'; break;
            case 'T': s[i] = '2'; break;
            case 'G': s[i] = '3'; break;
        }
    }
}

int main(){
    int qwq = 0;
    while(true){
        int n;
        read(n);
        if (n == 0) break;
        for(int i = 0; i < n; ++ i){
            scanf("%s",s);
            change(s);
            AC.insert(s);
        }
        AC.build();
        scanf("%s",s);
        change(s);
        int ans = AC.get_ans(s);
        ++ qwq;
        printf("Case %d: %d
",qwq,ans);
        AC.init();
    }
    return 0;
}

---

Best Sequence(POJ 1699)

题目大意

给定若干个字符串，要求构造一个字符串，使得它包含给定的字符串，且长度最小，输出最小长度。

解题思路

用给定的字符串构造一个AC自动机，那么我们构造的字符串要求在AC自动机上，从初始态出发，要求经过若干个指定点且步数最小。

这就是旅行商（TSP）问题。

状压(dp[i][j])表示当前表示出了的字符串的状态为(i)，最后一个表示的字符串是(j)（或者所在节点标号为(j)），的最小步数（长度）。

枚举下一个要构造的字符串（抵达的指定点）是哪个，转移即可。

由于点数（状态数）只有(200)，可以现在自动机上跑一遍(floyd)得到两点的距离。

注意一个节点所表示的状态(i)具有传递性，即节点(cur)恰是第(k)个字符串的结尾，即状态为(2^k)，那么(cur)的后继节点的状态也应该包括(2^k)。同时，如果(fail[cur])的状态包括第(j)个字符串，那么(cur)的状态也包括第(j)个字符串。

神奇的代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long LL;

template <typename T>
void read(T &x) {
    int s = 0, c = getchar();
    x = 0;
    while (isspace(c)) c = getchar();
    if (c == 45) s = 1, c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    if (s) x = -x;
}

template <typename T>
void write(T x, char c = ' ') {
    int b[40], l = 0;
    if (x < 0) putchar(45), x = -x;
    while (x > 0) b[l++] = x % 10, x /= 10;
    if (!l) putchar(48);
    while (l) putchar(b[--l] | 48);
    putchar(c);
}

class AC_automation{
    #define N 205
    #define M 4

    int trans[N][M]; 
    int fail[N];
    int sign[N];
    int pos[12];
    int dis[N][N];
    int dp[1028][12];
    int tot;
    int num;

    public:

    void init(){
        for(int i = 0; i <= tot; ++ i){
            fail[i] = sign[i] = 0;
            for(int j = 0; j < M; ++ j){
                trans[i][j] = 0;
            }
        }
        for(int i = 0; i < num; ++ i)
            pos[i] = 0;
        tot = num = 0;
    }

    void insert(const char * s){
        int cur = 0;
        for(size_t i = 0; s[i]; ++ i){
            if (! trans[cur][s[i] - '0']){
                trans[cur][s[i] - '0'] = ++ tot;
                sign[tot] |= sign[cur];
            }
            cur = trans[cur][s[i] - '0'];
        }
        sign[1<<num] |= 1;
        pos[num] = cur;
        num++;
    }

    void build(){
        queue<int> team;
        for(int i = 0; i < M; ++ i){
            if (trans[0][i]) team.push(trans[0][i]);
        }
        int u = 0;
        while(! team.empty()){
            u = team.front();
            team.pop();
            for(int j = 0; j < M; ++ j){
                if (trans[u][j]){
                    fail[trans[u][j]] = trans[fail[u]][j];
                    team.push(trans[u][j]);
                }else{
                    trans[u][j] = trans[fail[u]][j];
                }
            }
        }
    }

    void floyd(){
        for(int i = 0; i <= tot; ++ i)
            for(int j = 0; j <= tot; ++ j)
                dis[i][j] = 10000009;
        for(int i = 0; i <= tot; ++ i){
            for(int j = 0; j < M; ++ j){
                dis[i][trans[i][j]] = 1;
            }
            dis[i][i] = 0;
        }

        for(int k = 0; k <= tot; ++ k)
            for(int i = 0; i <= tot; ++ i) 
                for(int j = 0; j <= tot; ++ j){
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
    }

    int get_ans(){
        build();
        floyd();
        for(int i = 0; i < (1<<num); ++ i)
            for(int j = 0; j < num; ++ j)
                dp[i][j] = 10004;
        dp[0][0] = 0;
        for(int i = 0; i < num; ++ i)
            dp[1<<i][i] = dis[0][pos[i]];
        for(int i = 1; i < (1<<num); ++ i){
            for(int j = 0; j < num; ++ j){
                if (! ((i>>j)&1)) continue;
                for(int k = 0; k < num; ++ k){
                    if (((i>>k)&1)) continue;
                    dp[i | (1<<k)][k] = min(dp[i | (1<<k)][k], dp[i][j] + dis[pos[j]][pos[k]]);
                }
            }
        }
        int ans = 10004;
        for(int i = 0; i < num; ++ i)
            ans = min(ans,dp[(1<<num)-1][i]);
        return ans;
    }
}AC;


vector<string> s;

void change(string &s){
    for(size_t i = 0; s[i]; ++ i){
        switch(s[i]){
            case 'A': s[i] = '0'; break;
            case 'C': s[i] = '1'; break;
            case 'G': s[i] = '2'; break;
            case 'T': s[i] = '3'; break;
        }
    }
}

string qwq;

int n;

bool check(string & ss,int x){
    for(int i = x + 1; i < n; ++ i){
        size_t it = s[i].find(ss);
        if (! (it == string::npos)) return false;
    }
    return true;
}

bool cmp(const string &a, const string &b){
    if (a.size() < b.size()) return true;
    if (a.size() > b.size()) return false;
    return a<b;
}

int main(){
    int t;
    read(t);
    while(t--){
        s.clear();
        read(n);
        for(int i = 0; i < n; ++ i){
            cin>>qwq;
            change(qwq);
            s.push_back(qwq);
        }
        sort(s.begin(),s.end(),cmp);
        for(int i = n - 1; i >= 0; -- i){
            //if (check(s[i],i)) 
                AC.insert(s[i].c_str());
        }
        int ans = AC.get_ans();
        write(ans,'
');
        AC.init();
    }
    return 0;
}

当然也可以从根节点出发，SPFA式的状压搜索。

神奇的代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cmath>    
using namespace std;
typedef long long LL;

template <typename T>
void read(T &x) {
    int s = 0, c = getchar();
    x = 0;
    while (isspace(c)) c = getchar();
    if (c == 45) s = 1, c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    if (s) x = -x;
}

template <typename T>
void write(T x, char c = ' ') {
    int b[40], l = 0;
    if (x < 0) putchar(45), x = -x;
    while (x > 0) b[l++] = x % 10, x /= 10;
    if (!l) putchar(48);
    while (l) putchar(b[--l] | 48);
    putchar(c);
}

class AC_automation{
    #define N 205
    #define M 4

    int trans[N][M]; 
    int fail[N];
    int sign[N];
    int dp[N][1028];
    bool visit[N][1028];
    int tot;
    int num;

    public:

    void init(){
        for(int i = 0; i <= tot; ++ i){
            fail[i] = sign[i] = 0;
            for(int j = 0; j < M; ++ j){
                trans[i][j] = 0;
            }
        }
        tot = num = 0;
    }

    void insert(const char * s){
        int cur = 0;
        for(size_t i = 0; s[i]; ++ i){
            if (! trans[cur][s[i] - '0']){
                trans[cur][s[i] - '0'] = ++ tot;
            }
            sign[trans[cur][s[i] - '0']] |= sign[cur];
            cur = trans[cur][s[i] - '0'];
        }
        sign[cur] |= (1<<num);
        ++ num;
    }

    void build(){
        queue<int> team;
        for(int i = 0; i < M; ++ i){
            if (trans[0][i]) team.push(trans[0][i]);
        }
        int u = 0;
        while(! team.empty()){
            u = team.front();
            team.pop();
            for(int j = 0; j < M; ++ j){
                if (trans[u][j]){
                    fail[trans[u][j]] = trans[fail[u]][j];
                    sign[trans[u][j]] |= sign[fail[trans[u][j]]];
                    team.push(trans[u][j]);
                }else{
                    trans[u][j] = trans[fail[u]][j];
                }
            }
        }
    }

    int get_ans(){
        build();
        queue<pair<int,int> > team;
        for(int i = 0; i <= tot; ++ i){
            for(int j = 0; j < (1<<num); ++ j){
                dp[i][j] = 1028;
                visit[i][j] = false;
            }
        }
        team.push(make_pair(0,0));
        dp[0][0] = 0;
        visit[0][0] = true;
        while(! team.empty()){
            pair<int,int> u = team.front();
            team.pop();
            visit[u.first][u.second] = false;
            for(int i = 0; i < M; ++ i){
                pair<int,int> v = u;
                v.first = trans[u.first][i];
                v.second |= sign[trans[u.first][i]];
                if(dp[v.first][v.second] > dp[u.first][u.second] + 1){
                    dp[v.first][v.second] = dp[u.first][u.second] + 1;
                    if (! visit[v.first][v.second]){
                        team.push(v);
                        visit[v.first][v.second] = true;
                    }
                } 
            }
        }
        int ans = 1028;
        for(int i = 0; i <= tot; ++ i)
            ans = min(ans, dp[i][(1<<num) - 1]);
        return ans;
    }
}AC;

char s[25];

void change(char * s){
    for(size_t i = 0; s[i]; ++ i){
        switch(s[i]){
            case 'A': s[i] = '0'; break;
            case 'C': s[i] = '1'; break;
            case 'G': s[i] = '2'; break;
            case 'T': s[i] = '3'; break;
        }
    }
}

int main(){
    int t;
    read(t);
    while(t--){
        int n;
        read(n);
        while(n--){
            scanf("%s",s);
            change(s);
            AC.insert(s);
        }
        int ans = AC.get_ans();
        write(ans,'
');
        AC.init();
    }
    return 0;
}

---

Resource Archiver (HDU 3247)

题目大意

给定若干个(01)程序字符串，以及若干个(01)病毒字符串，要求构造一个字符串包含所有程序字符串但不包含任何病毒字符串，输出最小长度。

解题思路

根据这些(01)串构造一个AC自动机，题目抽象到自动机上就是要求从起点出发，不经过危险病毒点的情况下经过指定点，且要求步数最小。

也是一个旅行商问题，跟上题及其类似，但区别是这里状态数过多(有6万)，但我们实际考虑的最多只有那10个指定点，不能floyd我们只能从每个点出发BFS求出每个指定点（程序字符串）在不经过危险病毒点的情况下到达另一个指定点（程序字符串）的最小步数，然后跑一下状压dp即可。

注意某一点的所表示的字符串状态和危险也是可以传递的。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <typename T>
void read(T &x) {
    int s = 0, c = getchar();
    x = 0;
    while (isspace(c)) c = getchar();
    if (c == 45) s = 1, c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    if (s) x = -x;
}

template <typename T>
void write(T x, char c = ' ') {
    int b[40], l = 0;
    if (x < 0) putchar(45), x = -x;
    while (x > 0) b[l++] = x % 10, x /= 10;
    if (!l) putchar(48);
    while (l) putchar(b[--l] | 48);
    putchar(c);
}

class AC_automation{
    #define N 60003
    #define M 2

    int trans[N][M]; 
    int fail[N];
    int sign[N];
    int dp[1028][12];
    int pos[12];
    bool visit[N];
    int dis[12][12];
    int danger[N];
    int tot;
    int num;

    public:

    void init(){
        for(int i = 0; i <= tot; ++ i){
            fail[i] = sign[i] = danger[i] = 0;
            for(int j = 0; j < M; ++ j){
                trans[i][j] = 0;
            }
        }
        for(int i = 0; i < num; ++ i)
            pos[i] = 0;
        tot = num = 0;
    }

    void insert_resource(const char * s){
        int cur = 0;
        for(size_t i = 0; s[i]; ++ i){
            if (! trans[cur][s[i] - '0']){
                trans[cur][s[i] - '0'] = ++ tot;
            }
            sign[trans[cur][s[i] - '0']] |= sign[cur];
            cur = trans[cur][s[i] - '0'];
        }
        sign[cur] |= (1<<num);
        pos[num] = cur;
        ++ num;
    }

    void insert_virus(const char * s){
        int cur = 0;
        for(size_t i = 0; s[i]; ++ i){
            if (! trans[cur][s[i] - '0']){
                trans[cur][s[i] - '0'] = ++ tot;
            }
            cur = trans[cur][s[i] - '0'];
        }
        danger[cur] = 1;
    }

    void build(){
        queue<int> team;
        for(int i = 0; i < M; ++ i){
            if (trans[0][i]) team.push(trans[0][i]);
        }
        int u = 0;
        while(! team.empty()){
            u = team.front();
            team.pop();
            for(int j = 0; j < M; ++ j){
                if (trans[u][j]){
                    fail[trans[u][j]] = trans[fail[u]][j];
                    sign[trans[u][j]] |= sign[fail[trans[u][j]]];
                    danger[trans[u][j]] |= danger[fail[trans[u][j]]];
                    team.push(trans[u][j]);
                }else{
                    trans[u][j] = trans[fail[u]][j];
                }
            }
        }
    }

    int ddis[N];

    void get_dis(int x){
        dis[x][x] = 0;
        queue<int> team;
        team.push(pos[x]);
        for(int i = 0; i <= tot; ++ i){
            visit[i] = false;
            ddis[i] = 60050;
        }
        ddis[pos[x]] = 0;
        visit[pos[x]] = true;
        int u = 0;
        while(! team.empty()){
            u = team.front();
            team.pop();
            for(int v, i = 0; i < M; ++ i){
                v = trans[u][i];
                if (danger[v]) continue;
                if (!visit[v]){
                    ddis[v] = ddis[u] + 1;
                    team.push(v);
                    visit[v] = true;
                }
            }
        }
        for(int i = 0; i < num; ++ i){
            dis[x][i] = ddis[pos[i]];
        }
    }

    int get_ans(){
        build();
        pos[num] = 0;
        for(int i = 0; i <= num; ++ i){
            get_dis(i);
        }
        for(int i = 0; i < (1<<num); ++ i)
            for(int j = 0; j < num; ++ j)
                dp[i][j] = 60050;
        dp[0][0] = 0;
        for(int i = 0; i < num; ++ i)
            dp[1<<i][i] = dis[num][i];
        for(int i = 1; i < (1<<num); ++ i){
            for(int j = 0; j < num; ++ j){
                if (! (i>>j)&1) continue;
                for(int k = 0; k < num; ++ k){
                    if ((i>>k)&1) continue;
                    dp[i | (1<<k)][k] = min(dp[i | (1<<k)][k], dp[i][j] + dis[j][k]);
                }
            }
        }
        int ans = 600400;
        for(int i = 0; i < num; ++ i)
            ans = min(ans, dp[(1<<num) - 1][i]);
        return ans;
    }
}AC;

char s[50005];

int main(){
    while(true){
        int n,m;
        read(n);
        read(m);
        if (n == 0 && m == 0) break;
        while(n--){
            scanf("%s",s);
            AC.insert_resource(s);
        }
        while(m--){
            scanf("%s",s);
            AC.insert_virus(s);
        }
        int ans = AC.get_ans();
        write(ans,'
');
        AC.init();
    }
    return 0;
}