闲话
其实我也不太知道这个套路叫啥,他的过程就是DP和KMP的结合,毕竟是通过KMP来加速暴力匹配的过程,标题就写成KMP优化DP了.与之对应的还有一种AC自动机上优化的,其实两个套路一模一样,这里就只展示两个题,AC自动机的如果之后有空也会补上来.
设计密码
原题链接:Acwing1052
(由于acwing的题目上锁了,可能看不到,这个题是Indeedtokyo的19面试题,可能没得地方给评测)
题目大意:要求你构造一个长度为(n)的字符串(s),并且不包含子串(t).求(s)的方案数,对(10^9+7)取模.
此处不包含的定义是连续的一段不等于(t),不能是断开的几段拼起来是(t).
数据范围:
(1 leq n leq 50)
(1 leq |t| leq n)
思路
一个比较直接的想法肯定就是枚举了,不过既然方案数需要取模,说明方案数非常大,这个时候往往指向使用(dp)求方案数的思路.考虑设计状态:首先第一维肯定是保存当前构造到哪一位,同时我们还要知道现在具体匹配到(t)中的哪一个位置了,也就是当前这个位置肯定会和(t)产生字符串的匹配,问题就是现在连续的匹配到了谁的问题,这个东西肯定不好直接求,直接丢状态里.
那么可以写一下(dp)的具体流程了:
- 状态:(f[i][j])表示当前在(s)的第(i)位,并且(s[i])这一位填上某个元素之后,与(t)的匹配长度是(j)的方案数.
- 入口:(f[0][0]=0)其他全部置为(-infin).
- 转移:考虑(f[i][j])是由谁转移而来的是非常麻烦的,这里考虑当前这个状态(f[i][j])可以转移到哪个状态,那么枚举下一位,也就是(i+1)这一位具体要填什么字符,拿他去进一步和(t)进行匹配,匹配的一个新位置记作(u),那么下一个状态就是(f[i + 1][u]).显然当(u==|t|)时意味着(s)里面有一个子串(t)存在了,这种情况必须要删除.往下就可以写出方程形式:(f[i + 1][u] += f[i][j]).
- 出口:首先要做到最后一位,第一维肯定是(n),第二维只要保证不取(|t|)就可以了,直接把方案总和起来.
接着可以发现,这个枚举(s[i + 1])的取值,并且往后匹配的过程恰好就是拿(t)去做匹配,那么类似KMP处理就可以了.
不过这里其实有个出口第一维的取值的细节问题,下一个问题会考虑到,这个问题不太需要.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 55,MOD = 1e9 + 7;
char s[N],T[N];
int succ[N],f[N][N];
int main()
{
int n;scanf("%d",&n);
scanf("%s",T + 1);
int m = strlen(T + 1);
for(int i = 2,j = 0;i <= m;++i)
{
while(j && T[i] != T[j + 1]) j = succ[j];
if(T[i] == T[j + 1]) ++j;
succ[i] = j;
}
f[0][0] = 1;
for(int i = 0;i <= n;++i)
{
for(int j = 0;j < m;++j)
{
for(char k = 'a';k <= 'z';++k)
{
int u = j;
while(u && (u == n || k != T[u + 1])) u = succ[u];
if(k == T[u + 1]) ++u;
if(u < m) f[i + 1][u] = (f[i + 1][u] + f[i][j]) % MOD;
}
}
}
int res = 0;
for(int i = 0;i < m;++i) res = (res + f[n][i]) % MOD;
printf("%d",res);
return 0;
}
CF1163 D Mysterious Code
题目大意:有两个串(s)和(t)只包含小写字符,另有一个字符(c),其中包含小写字符或者*.现在要求你把*全部填上小写字符,并且规定两个字符串的牛逼操作(f(c,s)),他的值是(s)串在(c)中的出现次数,注意这里的出现次数跟上面那道题是一样连续的,而不是断开的.求(f(c,s) - f(c,t))的最大值.所有*位置必须填上字符,不可以空.
数据范围:
(1 leq |c| leq 1000)
(1 leq |s| ,|t| leq 50,s eq t)
思路
注意到较小的数据范围,接下来考虑直接dp:
-
状态:(f[i][j][k])表示当前(c)做到第(i)位,在(s)中的匹配位置是(j),在(t)中的匹配位置是(k).取得的(f(c,s)-f(c,t))的所有可能取值中的最大值.
-
入口:(f[1][0]=0)其他全部(-infin).
-
转移:与上面一致,如果当前这一位是
*则直接枚举取值,否则就直接按原有的值做.这里分别对两个串做匹配,记(j`,k`)分别是在(s)和(t)中下一位匹配到的新位置,只有当他们分别等于另一串的长度的时候才意味着匹配成功,当(s)匹配成功时权值增加一,同样(t)则减少一.直接转移即可. -
出口:第一维取(n+1)其他两维任选,取最大值即可.
这里的出口是有差别的,最开始把(c)这个串挪动成(1)开始的话,那么如果有串是枚举到(c)的最后一位,也就是(i=n)时才匹配上,那么他转移的时候,这一位本身要权值增加或者权值减少的,但是会把这个修改丢到(n+1)位上,所以最后一步等于说把本来该在这一位的移动到了下一位去,尽管下一位(c)并没有值,这是这种转移方式带来的.当然你也可以选择不把(c)设置从1开始,枚举的时候也从([0,n-1]),这个时候答案就要在(n)处统计了,可能看的好看点.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
const int N = 55,M = 1005;
char c[M];
int f[M][N][N];
struct kmp
{
char s[N],next[N];
int n;
void build()
{
next[1] = 0;
for(int i = 2,j = 0;i <= n;++i)
{
while(j > 0 && s[i] != s[j + 1]) j = next[j];
if(s[i] == s[j + 1]) ++j;
next[i] = j;
}
}
}s,t;
int main()
{
scanf("%s",c + 1);
int n = strlen(c + 1);
scanf("%s%s",s.s + 1,t.s + 1);
s.n = strlen(s.s + 1);t.n = strlen(t.s + 1);
s.build();t.build();
memset(f,-0x3f,sizeof f);
f[1][0][0] = 0;
forn(i,1,n) forn(j,0,s.n) forn(k,0,t.n)
{
for(char u = (c[i] == '*' ? 'a' : c[i]);u <= (c[i] == '*' ? 'z' : c[i]);++u)
{
int j_ = j,k_ = k;
while(j_ > 0 && (j_ == s.n || u != s.s[j_ + 1])) j_ = s.next[j_];
if(u == s.s[j_ + 1]) ++j_;
while(k_ > 0 && (k_ == t.n || u != t.s[k_ + 1])) k_ = t.next[k_];
if(u == t.s[k_ + 1]) ++k_;
int ct = (j_ == s.n) - (k_ == t.n);
f[i + 1][j_][k_] = max(f[i + 1][j_][k_],f[i][j][k] + ct);
}
}
int res = -1e9;
forn(j,0,s.n) forn(k,0,t.n) res = max(res,f[n + 1][j][k]);
printf("%d",res);
return 0;
}