首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >简单ac自动机学习

简单ac自动机学习

作者头像
ACM算法日常
发布2019-12-12 11:13:56
4790
发布2019-12-12 11:13:56
举报
文章被收录于专栏:ACM算法日常ACM算法日常

简单ac自动机学习

简单的来讲解一下自动机,虽然都在说这是和的组合,但个人觉得不需要深入理解这两个仍然可以学会它。同时由于网上已经存在了很多教程,本文尽量避免采取和网上一样的说法,加入一点自己在学习这个东西的时候的思考和理解,当然可能会存在错误,欢迎评论区指出。

首先对于,是一种存储字符串的结构,通常说的指树也就是字典树,其中状态当点,字母当边,代表状态到状态间的转移。

对于①,②,③,用表示大概这个样子。

image

接下来考虑往中读入一个串。

一开始我们处于,也就是状态0的位置,往中读入第一个字符,我们就位于状态1。

读入第二个字符,我们就位于状态。

读入第三个字串,我们就位于状态3。

读入第四个字符,我们就位于状态4。此时的状态4是一个终态,也就是一个串的末尾,这说明,读入的串中含有之前建立树的串。

以上就是的一些操作。

但是存在一个问题,就是如果串为,我们经过后到达状态3,下一个字符没有对应相应的状态转移,或者你不知道该往哪里走,或许你可以让它重新回到然后从第二个字符重新扫描,但这并不是最优的一种方式。显然,如果从第二个字符开始,串就变为。这样我们再继续一遍上面的操作就会发现我们会进入状态6(从,经过)。那么有没有什么方法能让我们直接从状态3直接跳到状态6呢?

我们注意到之所能够转跳是因为是串①的前缀的后缀,同时也是串②的前缀,这样就可以用中的思想建立指针,然后让中的每一个状态,对于字符集,中的每一个字符,都有一个对应的转跳位置,这样就解决了之前到达一个状态之后,对于读入的下一个字符没有地方转跳的困难,显然这样做的复杂度也是更好的。

另外一件很重要的事情

就是指针本身并不参与读入字符时状态之间的转跳,它只负责辅助将树变成一个图

如图一所示状态遇到时候没有转移的方向,这时候, 就应该顺着指针往上爬,爬到状态6,发现6可以往转移到7则直接讲3经过到7

image

其他具体的建立好一个自动机以后进行多模式匹配或者如何建立一个自动机,网上的教程很多,这里就不多讲了。

签到题就不放了,直接给一个自动机的套路的题。(好像是那一年北京的金牌题??)

Approximate Matching

Hihocoder 1877(ac自动机上dp) 2018 icpc北京H

题目

String matching, a common problem in DNA sequence analysis and text editing, is to find the occurrences of one certain string (called pattern) in a larger string (called text). In some cases, the pattern is not required to be exactly in the text, and minor differences are acceptable (due to possible typing mistakes). When given a pattern string and a text string, we say pattern P is approximately matched within text S, if there is a substring of S which is at most one letter different from P. Note that the length of this substring and the pattern must be identical. For example, pattern "abb" is approximately matched in text "babc" but not matched in "bbac".

It is easy to check if a pattern is approximately matched in a text. So your task is to count the number of all text strings of length m in which the given pattern can be approximately matched, and both of the patterns and texts are binary strings in order not to handle big integers.

题目大意

给出,和一个长度为的01字符串,问有多少个长度为的01字符串,在最多修改一位的情况下成为的子串。

输入

The first line of input is a single integer T (1 ≤ T ≤ 666), the number of test cases. Each test case begins with a line of two integers n,m (1 ≤ n,m ≤ 40), denoting the length of pattern string and text string. Then a single line of binary string P follows, which denotes the pattern. Note that there will be at most 15 test cases in which n ≥ 16.

输出

For each test case, output a single line with one integer, representing the answer.
5
3 4
110
4 7
1011 
2 10
00
7 17
1001110
11 22
11101010001
12
104
1023
72840
291544

题解

首先对于一个串来说每一位都可以修改,也可以不修改,所以共有种串可以成为的子串,这很容易想到是一个多模式的匹配,这样,把种串放入自动机中。

然后就是在自动机上的计数问题,但是如果考虑正面,我们就要考虑到上每个终止点对答案的贡献,这样太麻烦,所以不如直接考虑反面

为在自动机接受时,第步在不经过时走到的方案数

最后的答案就是

另外因为这道题的自动机中的所有串的长度相等,所以不用考虑指针指向终止结点的问题。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5+5;
const int MOD = 1e9+7;
#define mod(x) x % MOD
#define INF 0x3f3f3f3f

ll dp[41][maxn];
struct Trie{
    int nxt[maxn][26], fail[maxn], end[maxn];
    int root, L;
    int newnode(){
        for(int i = 0;i < 26;i++){
            nxt[L][i] = -1;
        }
        end[L++] = 0;
        return L-1;
    }
    void init(){
        L = 0;
        root = newnode();
    }
    void insert(char buf[]){
        int len = strlen(buf);
        int now = root;
        for(int i = 0; i < len;i++){
            if(nxt[now][buf[i] - '0'] == -1){
                nxt[now][buf[i] - '0'] = newnode();
            }
            now = nxt[now][buf[i] - '0'];
        }
        end[now]++;
    }
    void build(){
        queue<int> Q;
        fail[root] = root;
        for(int i = 0;i < 26 ;i++){
            if(nxt[root][i] == -1){
                nxt[root][i] = root;
            }
            else{
                fail[nxt[root][i]] = root;
                Q.push(nxt[root][i]);
            }
        }
        while(!Q.empty()){
            int now = Q.front();
            Q.pop();
            for(int i = 0;i < 26;i++){
                if(nxt[now][i] == -1){
                    nxt[now][i] = nxt[fail[now]][i];
                }
                else{
                    fail[nxt[now][i]] = nxt[fail[now]][i];
                    Q.push(nxt[now][i]);
                }
            }
        }
    }
    int query(char buf[]){
        int len = strlen(buf);
        int now = root;
        int res = 0;
        for(int i = 0;i < len;i++){
            now = nxt[now][buf[i] - '0'];
            int tmp = now;
            while(tmp != root){
                res += end[tmp];
                end[tmp] = 0;
                tmp = fail[tmp];
            }
        }
        return res;
    }
	void get_fail() {
        for(int i = 0;i < L;i++) {
            int to = fail[i], from = i;
            //G[i].push_back(to);
            //G[to].push_back(i);
        }
    }
    void debug(){
        for(int i = 0;i < L;i++){
            printf("id = %3d, fail = %3d, end = %3d, chi = [",i , fail[i], end[i]);
            for(int j = 0;j < 26;j++){
                printf("%2d", nxt[i][j]);
            }
            printf("]\n");
        }
    }
}ac;
char buf[maxn];
int main(){
    int t = 0;
    scanf("%d", &t);
    while(t--) {
        int n, m;
        scanf("%d %d", &n, &m);
        ac.init();
        scanf("%s", buf + 1);
        ac.insert(buf + 1);
        int len = strlen(buf + 1);
        for(int i = 1;i <= len;i++) {
            char tmp = buf[i];
            if(buf[i] == '0') buf[i] = '1';
            else buf[i] = '0';
            ac.insert(buf + 1);
            buf[i] = tmp;
        }
        ac.build();
        int cnt = ac.L;
        for(int i = 0;i <= m;i++) {
            for(int j = 0;j <= cnt;j++) {
                dp[i][j] = 0;
            }
        }
        int now = 0;
        dp[0][1] = 0, dp[0][0] = 1;
        for(int i = 0;i < m;i++) {
           for(int j = 0;j <= cnt;j++) {
               if(ac.end[j]) continue;
               for(int k = 0;k <= 1;k++) {
                   now = ac.nxt[j][k];
                   if(ac.end[now]) continue;
                   dp[i + 1][now] += dp[i][j];
               }
           }
        }
        ll ans = 1;
        for(int i = 1;i <= m;i++) {
            ans *= 2;
        }
        ll sum = 0;
        for(int i = 1;i <= ac.L;i++) {
            sum += dp[m][i];
        }
        printf("%lld\n", ans - sum);
    }
    return 0;
}

温馨提示

如果你喜欢本文,请分享到朋友圈,想要获得更多信息,请关注ACM算法日常

点赞的时候,请宠溺一点

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-12-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 简单ac自动机学习
  • Approximate Matching
  • Hihocoder 1877(ac自动机上dp) 2018 icpc北京H
    • 题目
      • 题目大意
        • 输入
          • 输出
            • 题解
              • 代码
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档