题目链接

首先特别感谢 灵茶山艾府 的 这篇文章，让我重新学了一下数位dp！
以及 官方题解！

没有学过kmp的小伙伴建议先去学一下。

这个题最重要最重要的就是状态的表示！

分析

首先是这个题目给的是一个范围[l,r]内求个数，一般来讲，数位dp都能利用前缀和的思想（区间有连续性）：
我们先求出[0,l-1]和[0,r]范围内合法的个数，然后ans[0,r] - ans[0,l-1]就行了。

然后还是一样的惯例，套用之前的模板；
但是我们发现我们在转移的过程中，可能需要记录前面构造的字符串；
但是又没有一种比较好的状态表示方法，比如状态压缩之类的…

此时我们回到题目本身，我们在构造的过程中只需要知道已构造的字符串和evil是否匹配就行；
结合数位dp从高位到地位的dp方式，其实在这个过程中我们相当于同时在遍历构造的字符串，然后同时判断和evil是否完全匹配；
这个过程是不是很熟悉？？？
没错，就很像kmp算法中的匹配过程！遍历长串然后和短串匹配！因此我们可以运用kmp算法。

kmp在匹配时的具体细节就是：
每次遍历长串s1[0 ~ n]的一个位置i，然后利用短串evil[0 ~ m]的next[]求出最大的j；
使得长串s1[0 ~ i]长度为j的后缀 和 短串evil长度为j的前缀匹配；
如果j到了短串evil的最后一个字符+1，则说明匹配成功。

因此，我们在记忆化搜索的过程中，也就是构造每一个字符时，加一个j的状态（意思如上所示），这里记为state；
对于记忆化搜索的状态如下：（板子参数）
i：当前填到哪一位；
state：构造到i-1位时和短串evil的最大匹配（意思同上）；
is_litmit： 前一位i-1是否填到了s[i-1]（上界）；
如果为true：则表示当前位i能填的上界是s[i]，否则是‘z’；

具体过程如下：

1. 递归出口（具体看代码）
2. 求出上界，枚举构造的字母ch，记忆化
   此时就要求出构造ch时的新状态new_state，具体其实就是kmp的匹配过程；

特别注意的是这里对 匹配字符串时的状态转移也进行了记忆化。

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
// #include 
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second

#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)
// #define int long long
// #define double long double
typedef long long ll;
typedef unsigned long long ull;
      
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;

const int maxn = 1e6 + 7;
const int N = 2e6 + 7;
const int M = 4e6 + 7;
const int mod = 1e9 + 7;
const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

//从这里开始----------------------------------------------------------------------------------

vector<int> ne;	//next数组，这里是从0开始的
string s1,s2,evil;
int m;

ll dp[550][55][2];
int mp[550][55];	//匹配字符串时的状态转移的记忆化

int get_state(int state,char ch)
{
	if(mp[state][ch-'a'] != -1) return mp[state][ch-'a'];
	
	//开始匹配
	while(state && evil[state] != ch) state = ne[state-1];
	
	mp[state][ch-'a'] = (evil[state] == ch ? state + 1 : 0);
	
	return mp[state][ch-'a'];
}

//数位dp，记忆化搜索
ll dfs(int i,int state,bool is_litmit,string s)
{
	//先判不合法的情况，前面构造的字符串已经出现和evil匹配
	if(state == evil.size()) return 0;	
	if(i == s.size()) return 1;	//合法，构造完了
	if(dp[i][state][is_litmit] != -1) return dp[i][state][is_litmit];
	
	ll ans = 0;
	char up = is_litmit ? s[i] : 'z';
	for(auto ch='a';ch<=up;ch++)
	{
		int new_state = get_state(state,ch);
		ans = (ans + dfs(i+1,new_state,is_litmit && ch==up,s)) % mod;
	}
	
	dp[i][state][is_litmit] = ans;
	
	return ans;
}

class Solution {
public:
    int findGoodStrings(int n, string _s1, string _s2, string _evil) {
		
		s1 = _s1;
		s2 = _s2;
		evil = _evil;
		
		int m = evil.size();
		vector<int> v(m);
		for(int i=1;i<m;i++)	//求next数组，从0开始
		{
			int j = v[i-1];
			while(j && evil[j] != evil[i]) j = v[j-1];
			
			if(evil[j] == evil[i]) v[i] = j+1;
		}
		ne = v;
		
		//求一下从aaa...到s2的合法字符串（不包含evil）个数
		memset(dp,-1,sizeof dp);
		memset(mp,-1,sizeof mp);
        ll ans2 = dfs(0,0,true,s2);
		
		//求一下从aaa...到s1的合法字符串（不包含evil）个数
        memset(dp,-1,sizeof dp);
		memset(mp,-1,sizeof mp);
		ll ans1 = dfs(0,0,true,s1);
		
		ll ans = (ans2-ans1+mod) % mod;	//利用前缀和减一下
		
		//判断一下s1是否合法，如果合法则加回来s1
        int f = 1;
        for(int i=0;i+m-1<s1.size();i++)
        {
            string s = s1.substr(i,m);
            if(s == evil)
            {
                f = 0;
                break;
            }
        }
        if(f) ans++;

		return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148