#include<iostream>
using namespace std;
struct Node{
	int id;
	Node *branch[26];
	Node(){
		id=-1;
		for(int i=0;i<26;i++)
			branch[i]=NULL;
	}
};
Node root;
//char dic[605][30];
char message[305];
int w,l,end;
int f[305];
void insert(char str[30],int id){
	Node *temp=&root;
	int index;
	for(int i=0,len=strlen(str);i<len;i++){
		index=str[i]-'a';
		if(temp->branch[index]==NULL)
			temp->branch[index]=new Node();
		temp=temp->branch[index];
	}
	temp->id=id;
}
int dp(int start){
	Node *temp=&root;
	int min=end-start+1,minTemp,d=0;
	int index=message[start]-'a';
	if(temp->branch[index]==NULL)//以message[start]打头的词根本不存在
		return 1+f[start+1];
	for(int i=start;i<=end;i++){
		index=message[i]-'a';		
		//遇到不存在的，则跳过，d++
		if(temp->branch[index]==NULL){
			d++;			
		}else{
			temp=temp->branch[index];
			//trie中对应id不为-1，即找到一个单词			
			if(temp->id!=-1){
				minTemp=d+f[i+1];
				if(minTemp<min) 
					min=minTemp;				
			}
			//trie中对应不为NULL但为-1
		}
		minTemp=i-start+1+f[i+1];//每一步都要判断！！！必须的！！！！
		if(minTemp<min)
			min=minTemp;
	}
	return min;
}
int main(){
	int i;
	char str[30];
	scanf("%d%d",&w,&l);
	scanf("%s",&message);
	for(i=1;i<=w;i++){
		//scanf("%s",dic[i]);
		//insert(dic[i],i);
		scanf("%s",&str);
		insert(str,i);
	}
	end=strlen(message)-1;
	for(i=end;i>=0;i--)
		f[i]=dp(i);
	printf("%d\n",f[0]);
	system("pause");
	return 0;
}
/*
下面是WA的一组数据：
40 50
owoooccccwococoowcoowowwccowwoocoowcowocwccwoowwwc
cwowocwwoo
occccwococ
cowcwcowwwoow
wocowwowww
oowwcccocwowc
cwoooowoowowww
cwwooccc
coocwcowowowc
wcwowwowo
owwowwoc
oooowwcwoow
wwcoocccwwo
owowoooo
wocccwwooow
ccwwwoocwwc
wwwcwwwccwww
wwowwococ
ccwwcwcc
cowwccwwccow
cwocowoccc
wowwwwwcw
ocwowwcwo
oowowoowwcc
ooccoccwww
coowwcccwooo
ooccwoooccc
oocwccwowco
cwccwcooc
wwocwoooocwwo
cwocowwccocwcwc
wwooccwowwo
cccccowcwc
ocwccwcwco
coccowocc
owwwcooowowwc
wwwocwowcoc
cowoccoooco
wwwowcoccwc
cwcowowooc
cwooowwwc
20
*/

• Re:trie+从后往前的dp 少部分测试数据WA 哪位大牛帮忙看下哪里出了问题 附数据 (2360) feir8510 2009-12-29 15:55:21
• Re:trie+从后往前的dp 少部分测试数据WA 哪位大牛帮忙看下哪里出了问题 附数据 (20) hjp 2010-05-04 02:19:53