博客

题意

一种语言有N种字符，一句话的长度为M，有P个禁止说的字符串。问能生成多少种可以说的字符串。

题解

看到这道题，第一眼就能想到是矩阵+AC自动机，于是果断MLE。后来看了题解才意识到这道题的数据范围小，所以DP完全可以解决，也不用构造什么矩阵了。对于不允许的字符串节点，直接continue就可以了。

注意事项

各种RE,WA,MLE。需要特别注意的是编码问题，编码一定要用“ISO-8859-1”。开始我用的是“UTF8”编码，然后一直WA，ORZ。。。

代码

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Iterator;
import java.util.Queue;
import java.util.Scanner;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(new BufferedInputStream(System.in), "ISO-8859-1");
        AC ac = new AC();
        ac.n = scanner.nextInt();
        ac.m = scanner.nextInt();
        ac.p = scanner.nextInt();
        scanner.nextLine();
        ac.init();
        String string = scanner.nextLine();
        // System.out.println(string);
        for (int i = 0; i < ac.n; i++) {
            char c = string.charAt(i);
            ac.mp[c] = i;
        }
        for (int i = 0; i < ac.p; i++) {
            ac.st = scanner.nextLine();
            ac.insert();
        }
        ac.getFail();
        BigInteger dp[][] = new BigInteger[55][120];
        for (int i = 0; i <= ac.m; i++) {
            for (int j = 0; j < ac.sz; j++) {
                dp[i][j] = new BigInteger("0");
            }
        }
        dp[0][0] = new BigInteger("1");
        for (int i = 0; i < ac.m; i++) {
            for (int j = 0; j < ac.sz; j++) {
                for (int k = 0; k < ac.n; k++) {
                    int x = ac.ch[j][k];
                    if (dp[i + 1][x] == null)
                        continue;
                    if (ac.val[x] != 0)
                        continue;
                    dp[i + 1][x] = dp[i + 1][x].add(dp[i][j]);
                }
            }
        }
        BigInteger ans = new BigInteger("0");
        for (int i = 0; i < ac.sz; i++) {
            ans = ans.add(dp[ac.m][i]);
            // System.out.println(dp[ac.m][i]);
        }
        System.out.println(ans);
    }
}

class AC {
    int mp[];
    int ch[][];
    int val[], f[];
    int sz;
    int n, m, p;
    String st;

    void init() {
        sz = 1;
        mp = new int[66000];
        ch = new int[150][55];
        val = new int[150];
        f = new int[150];
    }

    void insert() {
        int u = 0;
        int len = st.length();
        // System.out.println(len);
        // System.out.println(st);
        for (int i = 0; i < len; i++) {
            int x = mp[st.charAt(i)];
            // System.out.println(x);
            if (ch[u][x] == 0) {
                ch[u][x] = sz++;
            }
            u = ch[u][x];
        }
        val[u] = 1;
    }

    void getFail() {
        LinkedBlockingQueue<Integer> q = new LinkedBlockingQueue<Integer>();
        for (int i = 0; i < n; i++) {
            if (ch[0][i] != 0) {
                q.add(ch[0][i]);
            }
        }
        while (q.peek() != null) {
            int r = q.peek();
            q.poll();
            for (int i = 0; i < n; i++) {
                int x = ch[r][i];
                if (x == 0) {
                    ch[r][i] = ch[f[r]][i];
                    continue;
                }
                q.add(x);
                int v = f[r];
                f[x] = ch[v][i];
                val[x] |= val[f[x]];
            }
        }
    }
}

/*
 * 4 3 4 ACGT AT AC AG AA
 */