POJ 3267：The Cow Lexicon 字符串匹配dp

The Cow Lexicon

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 8905		Accepted: 4228

Description

Few know that the cows have their own dictionary with W (1 ≤ W ≤ 600) words, each containing no more 25 of the characters 'a'..'z'. Their cowmunication system, based on mooing, is not very accurate; sometimes they hear words that do not make any sense. For instance, Bessie once received a message that said "browndcodw". As it turns out, the intended message was "browncow" and the two letter "d"s were noise from other parts of the barnyard.

The cows want you to help them decipher a received message (also containing only characters in the range 'a'..'z') of length L (2 ≤ L ≤ 300) characters that is a bit garbled. In particular, they know that the message has some extra letters, and they want you to determine the smallest number of letters that must be removed to make the message a sequence of words from the dictionary.

Input

Line 1: Two space-separated integers, respectively: W and L
Line 2: L characters (followed by a newline, of course): the received message
Lines 3..W+2: The cows' dictionary, one word per line

Output

Line 1: a single integer that is the smallest number of characters that need to be removed to make the message a sequence of dictionary words.

Sample Input

6 10
browndcodw
cow
milk
white
black
brown
farmer

Sample Output

题意是给出一个主串，给出一系列的字典单词，问从主串中最少删除多少个字符，使得主串都是有字典里的单词组成的。

自己感觉这个dp和暴力也差不太多了。

dp[x]表示从主串第一个字符到主串第x-1个字符要删除的数量。然后对于主串中的每一个位置，都对字典中的单词向前匹配，如果位置j 到位置i 匹配单词k成功，就比较一下当前的值与i-j-len[k]+dp[j]的值。取其最小值。

感觉是一个很好理解的dp，但真做反正我没想到。。。

代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;

int W, L;
string message;
string word[605];
int len[605];
int dp[305];

int main()
{	
	int i, j, k;
	cin >> W >> L;
	cin >> message;

	for (i = 1; i <= W; i++)
	{
		cin >> word[i];
		len[i] = word[i].length();
	}
	for (i = 0; i < L; i++)
	{
		if (i == 0)
			dp[0] = 1;
		else
			dp[i] = dp[i - 1] + 1;
		
		for (k = 1; k <= W; k++)
		{
			int subs = len[k] - 1;
			int temp = i;
			if (subs > i)
				continue;
			while (subs >= 0 && temp >= 0 && temp>=subs)
			{
				if (message[temp] == word[k][subs])
					subs--;
				temp--;
			}
			if (subs < 0)
			{
				dp[i] = min(dp[i],i-temp-len[k]+dp[temp]);
			}
		}
	}
	cout << dp[i - 1] << endl;
	return 0;
}