#include <iostream>
#include <stdio.h>
#include <cstring>
#define L 310
#define W 610
using namespace std;
char b[W][L],a[L];
int c[W],lena,lenb,dp[L];
int main()
{
int i,w,m,k,j;
scanf("%d %d",&w,&lena);
scanf("%s",a);
for(i=0;i<w;i++)
{scanf("%s",b[i]);c[i]=strlen(b[i]);}
for (i=1;i<=lena;i++)
{
dp[i]=dp[i-1]+1;    //dp[i]表示前i个字符中需要删除的字符的个数
for (m=0;m<w;m++)
{
k=c[m]-1;
for (j=i-1;j>=0 && k>=0;j--)     
if (a[j]==b[m][k])
k--;
if (k<0)
dp[i]=min(dp[i],dp[j+1]+i-1-j-c[m]);    //i-1为j的初值，i-1-j为j走过的长度，而c[m]为模式串的长度，相减即为要删除的字符的个数
}
}
cout<<dp[lena]<<endl;
return 0;
}

转载于:https://www.cnblogs.com/You-Change/p/3415023.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/96888547

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。