题目描述
小豆参加了生物实验室。在实验室里，他主要研究蛋臼质。他现在研究的蛋臼质是由k个氨基酸按一定顺序构成的 。每一个氨基酸都可能有a种碱基序 列si_j 构成。现在小豆有一个碱基串s，小豆想知道在这个碱基上都多少中 不同的组合方式可能得到这个蛋白质。即求由k段字符串有序合并成的字符串s1,有多少种不同方式能够匹配字符串 s，其中k段字符串的选法不同，或者与s匹配上 的位置不同认为是不同的方式。
输入格式
第一行一个数，表示这个蛋臼质由k个氨基酸。 第二行一个字符串s，表示小豆现在有的碱基串。 第三行开始接下来k行表示第i个氨基酸可能的碱基序列，对于第i个氨基酸，ai表示这个氨基酸可能的碱基序列种数， 接下来ai个字符串表示这ai 种可能的碱基序列，用空格隔开。 1 ≤ k ≤ 100, |s| ≤ 10000,ai ≤ 10
输出格式
输出一个数目表示不同的方案数 (不同的方案数是指不同的子碱基串或者相同的碱基串不同的氨基酸排列方式) 答案对1e9+7取模
样例
样例输入
2
ABC
2 A AB
2 C BC
样例输出
2
我他妈就是弱智
感谢wlesq的题解
这是一道hash+背包DP（很显然我没发现），如果当前选出的子串可以匹配，就可以从字符串相对应的子串的前一位置的状态转移过来（注意，我说的是子串第一位的前一位），不懂的看下图
f[r-len+1]是没有数的，f[r]的上一个状态是f[r-len]
f[i][j]表示前i长的主串匹配了第j列的碱基的情况
\(f[i][j]+=f[i-len_{j,k}] [j-1]\)(hash(s1)==hash(\(s_{j,k}\)))
然后没了，关于前缀求子串可以看乌力波，谴责wlesq速速修改题解
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int base=131;
const int mod=1e9+7;
int n,m;
char s[12000];
char c[120][15][1000];
long long f[12000][120];
ull has[12000];
int num[120];
ull bas[12000];
void get(){
int len=strlen(s+1);
for(int i=1;i<=len;i++){
has[i]=has[i-1]*base+s[i];
}
bas[0]=1;
for(int i=1;i<=len;i++){
bas[i]=bas[i-1]*base;
}
}
ull gethash(int from,int to){
return has[to]-has[from-1]*bas[to-from+1];
}
ull check(char si[]){
ull res=0;
int len=strlen(si+1);
for(int i=1;i<=len;i++){
res=res*base+si[i];
}
return res;
}
int main(){
cin>>n;
scanf("%s",s+1);
for(int i=1;i<=n;i++){
cin>>m;
num[i]=m;
for(int j=1;j<=m;j++){
scanf("%s",c[i][j]+1);
}
}
get();
int lensum=strlen(s+1);
for(int i=0;i<=lensum;i++) f[i][0]=1;
for(int i=1;i<=n;i++){
for(int k=1;k<=num[i];k++){
int len2=strlen(c[i][k]+1);
// for(int j=1;j<=len2;j++){
// cout<<c[i][k][j];
// }
for(int j=lensum;j>=len2;j--){
if(check(c[i][k])==gethash(j-len2+1,j)){
f[j][i]=(f[j][i]+f[j-len2][i-1])%mod;
// cout<<f[j][i]<<" "<<f[j-len2][i-1]<<" ";
}
}
// cout<<endl;
}
}
long long ans=0;
for(int i=1;i<=lensum;i++){
ans=(ans+f[i][n])%mod;
}
cout<<ans%mod<<endl;
}
对了，我用vector+string没调出来，有大佬能否看一下
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef signed long long ull;
vector<string> q[120];
ull has[12000],bas[12000];
long long f[12000][120];
const int base=131,mod=1e9+7;
int n,m;
string s,c;
void solve(){
bas[0]=1;
has[0]=s[0];
for(int i=1;i<s.length();i++){
has[i]=has[i-1]*base+s[i];
}
for(int i=1;i<=10000;i++) bas[i]=bas[i-1]*base;
}
long long check(string lm){
ull res=0;
for(int i=0;i<lm.length();i++){
res=res*base+lm[i];
}
return res;
}
long long find(int from,int to){
if(from<=0) return has[to];
return (has[to]-has[from-1]*bas[to-from+1]);
}
int main(){
cin>>n;
cin>>s;
solve();
for(int i=1;i<=n;i++){
cin>>m;
for(int j=1;j<=m;j++){
cin>>c;
q[i].push_back(c);
}
}
// cout<<q[2].size()<<endl;
// cout<<s.length();
for(int i=0;i<s.length();i++) f[i][0]=1;
for(int i=1;i<=n;i++){
int len1=q[i].size()-1;
for(int k=0;k<=len1;k++){
int len=q[i][k].length();
int len3=s.length()-1;
for(int j=len3;j>=len-1;j--){
if(check(q[i][k])==find(j+1-len,j)){
if(j-len<=0) f[j][i]+=f[0][i-1];
else f[j][i]+=f[j-len][i-1];
// cout<<j<<" "<<i<<" "<<f[j][i]<<" ";
// cout<<"|||";
}
}
}
// cout<<endl;
}
// cout<<endl;
// cout<<endl;
long long ans=0;
// for(int i=0;i<s.length();i++){
// for(int j=1;j<=n;j++){
// cout<<f[i][j]<<" ";
// }
// cout<<endl;
// }
for(int i=0;i<s.length();i++){
ans+=f[i][n];
}
cout<<ans%mod<<endl;
}