#include <iostream>
#include <string>
#include <memory.h>
using namespace std;
int wordnum;
int sentencelength;
string sentence;
string dict[601];
int dp[601];
int main()
{
	cin>>wordnum>>sentencelength;
	cin>>sentence;
	for(int i=1;i<=wordnum;i++)
	{
		cin>>dict[i];
	}
	memset(dp,0,sizeof(dp));
	for(int i=sentencelength-1;i>=0;i--)
	{
		dp[i]=dp[i+1]+1;
		for(int j=1;j<=wordnum;j++)
		{
			string word=dict[j];
			if(sentencelength-i>=word.length())
			{
				//开始匹配
				int m,n;
				m=i;//从主串开始找,直到sentencelength
				n=0;//从word开始找，直到word.length()
				while(m<=sentencelength-1&&n<=word.length()-1)
				{
					if(sentence[m]==word[n])
					{
						m++;
						n++;
					}
					else
						m++;
					
					
				}
				if(n==word.length()&&dp[i]>dp[m]-i+m-word.length())
				{
					dp[i]=dp[m]-i+m-word.length();					
				}
			}
		}
	}
	cout<<dp[0]<<endl;
	//system("pause");
	return 0;
}

• Re:贴个代码备忘 (1047) lj19900425 2013-03-12 18:23:57