简单ac自动机学习

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.

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;
}