2351757_ac_232ms_80k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int w, l;
char mes[301];
char dic[601][27];
int best[301];

int main()
{
	int i, j, k, p, t;

	scanf("%d%d%s",&w,&l,mes);
	for(i = 0; i < w; i++)
		scanf("%s",dic[i]);
	for(i = 0; i <= l; i++)
		best[i] = i;
	for(i = 0; i < l; i++)
	{
		for(j = 0; j < w; j++)
		{
			if(i+strlen(dic[j])<=l)
			{
				if(dic[j][0]==mes[i])
				{
					p = i;t = 0;
					for(k = 0; k < strlen(dic[j]); k++)
					{
						while(mes[p]!=dic[j][k])
						{
							p++;t++;
							if(p>=l) 
								goto con;
						} 
						p++;
					}
					if (best[i]+t<best[p]) best[p]=best[i]+t;
				}
			}
			con:;
		}
		if(best[i]+1<best[i+1])
			best[i+1] = best[i]+1;
	}
	printf("%d\n",best[l]);
	return 1;
}