欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

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

程序员文章站 2022-05-04 11:58:13
题目链接题目描述你现在需要设计一个密码 S,S 需要满足:S 的长度是 NS 只包含小写英文字母S 不包含子串 T例如:abc 和 abcde 是 abcde 的子串,abd 不是 abcde 的子串。请问共有多少种不同的密码满足要求?由于答案会非常大,请输出答案模 109+7 的余数。f[i][j]f[i][j]f[i][j]定义到第i位密码位置与子串T匹配长度为j时的密码数目。要求的答案为∑j=0m−1f[N][j]\sum_{j=0}^{m-1}f[N][j]j=0∑m−1...

题目链接

题目描述

你现在需要设计一个密码 S,S 需要满足:

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

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

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

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

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

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

#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