CF1729G Cut Substrings
给出两个字符串 \(s,t\)，每次可以将字符串 \(s\) 中任意一个为 \(t\) 的子串删除，删除位置的字符变为空格（或理解为无实义）。求最少删除几次可以使得字符串 \(s\) 中不会出现字符串 \(t\)，以及在这个最小次数下的方案数。\(1\leq |s|,|t|\leq 500\)。
给出一种与官方题解相同的做法。
题解
首先可以先用字符串匹配算法算出 \(s\) 中每个与 \(t\) 相同的子串的出现位置 \(pos\)，记第 \(i\) 次出现的位置为 \(pos_i\)。
定义 \(f_i,dp_i\) 分别为删除以原字符串 \(pos_i\) 下标开始的与 \(t\) 相同的子串后，使得原字符串 \({1\sim pos_i}\) 下标范围内对应新字符串中不存在 \(t\) 子串的最小操作数和方案数。
假设删除 \(pos_i\) 开始的一个子串后，存在一个 \(j>i\)，使得原字符串下标 \(pos_i\sim pos_j-1\) 范围内对应的新的字符串中不存在一个 \(t\)。那么可以得到转移。
\[f_j\gets f_i+1\\ dp_j\gets \begin{cases}\begin{align} dp_i &\quad f_i\neq f_i+1\\ dp_i+dp_j&\quad f_j=f_i+1 \end{align}\end{cases} \]实现
假设 \(pos\) 位置一共有 \(tot\) 个，容易发现 \(pos_{tot}\) 开始的子串不一定要被删除。所以我们建立一个必须被删除的无实义节点 \(pos_{tot+1}=n+m\)。最后输出 \(f_{tot}-1\) 和 \(dp_{tot}\)。
现在的问题是找到满足条件的 \(j\)。
容易发现删除 \(pos_i\) 开始的子串后，\(\forall pos_k\leq pos_{i}+|t|-1\) 均不会作为一个完整的 \(t\) 出现在目前 \(s\) 中。找到最小的 \(l\)，使得 \(pos_l>pos_i+|t|-1\)，那么 \(pos_l\leq pos_j\leq pos_l+|t|-1\)，才能使得 \(pos_l\) 开始的子串不再出现。
其他细节具体见代码，时间复杂度 \(O(n^2)\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int>ttfa;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
const ll MOD=1000000007;
const int N=503;
char s[N],t[N];
int n,m,f[N],pos[N],tot;
ll dp[N];
inline void Tesc(){
memset(f,0x3f,sizeof(f));
memset(dp,0,sizeof(dp));
scanf("%s%s",s+1,t+1);
n=strlen(s+1),m=strlen(t+1),tot=0;
for(int i=1;i+m-1<=n;++i){
bool flag=1;
for(int j=1;j<=m;++j)
if(s[i+j-1]!=t[j])
{flag=0;break;}
if(flag)pos[++tot]=i;
}
f[0]=0,dp[0]=1;pos[0]=-114514,pos[++tot]=n+m;
for(int i=0;i<tot;++i){
int loc=i+1;
while(loc<=tot&&pos[loc]<=pos[i]+m-1)++loc;
for(int j=loc;j<=tot&&pos[j]<=pos[loc]+m-1;++j){
if(f[i]+1<f[j]){
f[j]=f[i]+1;
dp[j]=dp[i];
}else if(f[i]+1==f[j])dp[j]=(dp[j]+dp[i])%MOD;
}
}
printf("%d %lld\n",f[tot]-1,dp[tot]);
}
int main(){
int T=read();
while(T--)Tesc();
return 0;
}