很明显,这是一道DP题目。
状态如下:
假如字符串为str1,字典为str。
对于str1从尾到头查找
dp[i]=dp[i+1]+1;//str1[i]!=str[0];
dp[i]=min(dp[i],,dp[l1]+(l1-i)-len);//str1[i]==str[0]&&str1第i个字符以后可以匹配str,l1为匹配完str所到的位置
程序:
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define min(a,b) a<b?a:b
int main()
{int w,l,i,j;while(scanf("%d%d%*c",&w,&l)!=EOF){char str1[10000];char str[601][1000];int dp[10001];gets(str1);for(i=0;i<w;i++)gets(str[i]);dp[l]=0;for(i=l-1;i>=0;i--){dp[i]=dp[i+1]+1;for(j=0;j<w;j++){int len=strlen(str[j]);if(len<=l-i && str[j][0]==str1[i]){ int l1=i; int l2=0; while(l1<l) {if(str[j][l2]==str1[l1++])l2++;if(l2==len){ dp[i]=min(dp[i],dp[l1]+(l1-i)-len);break; } }}}}cout<<dp[0]<<endl;}return 0;
}