调了一晚上,要红温了 a[2][1]值大于0??? 不知道怎么更新到的
#include<bits/stdc++.h>
#define int long long
using namespace std;
int pp,k;
unsigned int b[200010];
const int base=131,mod=194910017;
char c[2010];
int a[210][110];
int dp[210][210];
int le[2010];
unsigned int hash1[200010];
unsigned int mp[200010];
unsigned int get(int l,int r){
return hash1[r]-hash1[l-1]*b[r-l+1];
}
bool get_hash(int l,int r){
for(int i=1;i<=pp;i++){
if(get(l,min(l+le[i]-1,r))==mp[i]){
if(l==109&&r==1) cout<<mp[i]<<" ";
return 1;
}
}
return 0;
}
unsigned int hsh(string s){
unsigned int ans=0;
int len=s.size();
for(int i=1;i<=len;i++){
ans=(ans*base+s[i-1]);
// cout<<ans<<' ';
}
return ans;
}
signed main(){
int n;
cin>>n>>k;
int len=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=20;j++){
cin>>c[++len];
}
}
b[0]=1;
for(int i=1;i<=len;i++){
b[i]=(b[i-1]*base);
//cout<<c[i]<<' ';
hash1[i]=(hash1[i-1]*base+c[i]);
// cout<<hash1[i]<<' '
; }
cin>>pp;
string s;
for(int i=1;i<=pp;i++){
cin>>s;
le[i]=s.size();
mp[i]=hsh(s);
// cout<<mp[i]<<' '<<le[i]<<'\n';
}
memset(a,0,sizeof(a));
for(int i=len;i>=1;i--){
for(int j=i;j>=1;j--){
a[j][i]=a[j+1][i];
// cout<<a[j][1]<<" ";
if(get_hash(j,i)){
// cout<<1;
a[j][i]++;}
// if(i==1)
// cout<<a[j][i]<<' ';
}
}
// cout<<get_hash(109,1)<<' ';
// for(int i=1;i<=len;i++){
// cout<<a[i][1]<<" ";
// }
for(int i=1;i<=len;i++){
dp[i][1]=a[1][i];
// cout<<a[1][i]<<" ";
for(int j=2;j<=k;j++){
for(int p=1;p<i;p++){
if(dp[p][j-1])
dp[i][j]=max(dp[i][j],dp[p][j-1]+a[p+1][i]);
}
}
}
cout<<dp[len][k];
return 0;
}