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(chǎn)’..’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(chǎn)’..’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

Sample Output

題意

給出一個(gè)原始序列，以及w個(gè)單詞，問該序列至少需要去掉多少個(gè)字母之后，才能變成完全由已知單詞構(gòu)成的序列。

思路

從題目可以分析出，我們需要找到該序列對(duì)于所有單詞的最大不重合匹配數(shù)，然后需要?jiǎng)h除的字母個(gè)數(shù)便是序列長度減去匹配數(shù)。

對(duì)于匹配這一動(dòng)作，我們需要從前向后匹配單詞的字母，但是狀態(tài)數(shù)組中存儲(chǔ)的結(jié)果，如果也是從前往后更新的話會(huì)造成提前更新或者其他操作，因此我們對(duì)于序列采取從后向前遍歷的方法。

dp[i]代表序列[i,n-1]中最少刪除的字母個(gè)數(shù)。

首先對(duì)于遍歷到的每一位，先取最壞情況，此時(shí) dp[i]=dp[i+1]+1$dp[i]=dp[i+1]+1$

然后遍歷字典，找出所有首字母和序列當(dāng)前字母相同的單詞，然后進(jìn)行匹配，若成功匹配該單詞后更新 dp[i]$dp[i]$

其中： dp[i]=min(dp[i],dp[si]+si?i?len)$dp[i]=min(dp[i],dp[si]+si-i-len)$

si 為匹配單詞結(jié)束后的序列游標(biāo)，i為匹配前的序列游標(biāo)，len為單詞長度

AC 代碼