操作:从字符串a中扣除给定的子串b(如hebheof 和 he ,结果 --bheof或heb--of
问直到无法操作时,至少需要几次
#include<iostream>
#include <vector>
#include <cstring>
using namespace std;const int mod=1e9+7;const int N=1e3;int n,m,f[N],cnt[N];string a,b;void solve(){int i,j,k; vector<int> v;n=a.length(); m=b.length(); a="0"+a;v.push_back(0);for(i=1;i+m-1<=n;i++){if(a.substr(i,m)==b) v.push_back(i+m-1);}memset(f,0x3f3f3f3f,sizeof f); memset(cnt,0,sizeof cnt);f[0]=0,cnt[0]=1;//for(i=0;i<v.size();i++) cout<<v[i]<<' ';for(i=1;i<v.size();i++)for(j=i-1;j>=0;j--){if(v[i]-v[j]<m) continue;int flag=0;for(k=j+1;k<i;k++)if(v[k]-v[j]>=m&&v[i]-v[k]>=m) flag=1;if(flag) break;if(f[j]+1<f[i]) f[i]=f[j]+1,cnt[i]=cnt[j];else if(f[j]+1==f[i]) cnt[i]+=cnt[j],cnt[i]%=mod; }int mn=1<<30,t=0;for(i=0;i<v.size();i++) if(v.back()-v[i]<m) mn=min(mn,f[i]);for(i=0;i<v.size();i++)if(v.back()-v[i]<m&&f[i]==mn) t+=cnt[i]; cout<<mn<<' '<<t%mod<<endl;}int main(){int T; cin>>T;while(T--)cin>>a>>b,solve();}