AcWing1052设计密码(IndeedTokyo2019校招笔试题)(kmp+dp)

题目链接

题目描述

你现在需要设计一个密码 S，S 需要满足：

• S 的长度是 N
• S 只包含小写英文字母
• S 不包含子串 T

例如：abc 和 abcde 是 abcde 的子串，abd 不是 abcde 的子串。
请问共有多少种不同的密码满足要求？
由于答案会非常大，请输出答案模 109+7 的余数。

$f[i][j]$定义到第i位密码位置与子串T匹配长度为j时的密码数目。

要求的答案为
$\sum_{j=0}^{m-1}f[N][j]$
其中$m$为禁止串$T$长度。

这是一个状态机问题。
首先对于加在第$i+1$位的字母有26个选择，对于不同字母$k$的选择，假定当前状态为$(i,j)$（第$i$位为止与$T$串匹配的长度为$j$），其下一个状态（即加上这个字母后与$T$串匹配的长度）我们定义为$dfa[j][k]$(类似于有穷状态自动机的东西)，那么我们就可以得到状态转移的方程
$f[i+1][dfa[j][k]] \ += f[i][j]$

只需要提前预处理出$dfa$即可。

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int mod = 1e9+7;
char T[60];
int nxt[60], dfa[60][60];
LL f[60][60];

int main() {
	int n, m;
	cin >> n;
	cin >> (T+1);
	m = strlen(T+1);
	for (int i = 2, j = 0; i <= m; i++) {
		while(j && T[j+1] != T[i]) j = nxt[j];
		if (T[j+1] == T[i]) j++;
		nxt[i] = j;
	}
	// 不预处理dfa也可，效率会低一些。
	for (int j = 0; j < m; j++) {
	    for (int k = 0; k < 26; k++) {
	        int t = j;
	        while (t && T[t+1] != k + 'a') t = nxt[t];
	        if (T[t+1] == k + 'a') t++;
	        dfa[j][k] = t;
	    }
	}
	
	f[1][0] = 25, f[1][1] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < 26; k++) {
            	// 利用dfa进行状态转移
                f[i+1][dfa[j][k]] = (f[i+1][dfa[j][k]] + f[i][j]) % mod; 
            }
        }
    }
    
    LL res = 0;
    for (int i = 0; i < m; i++) res = (res + f[n][i]) % mod;
    cout << res << endl;
	return 0;
}

本文地址：https://blog.csdn.net/weixin_43359565/article/details/107611073