ZOJ Problem Set - 3013
One key technology in Chinese search engine is Word Segmenting, which is more difficult than English Word Segmenting, as there is no space between words.
A traditional solution is Forward Maximum Match (FMM) or Backward Maximum Match(BMM). The FMM alogrithm goes forward from the begining of the passage, selecting the word with the maximum length as the current match word from the word library, and jump to the word's next position, of course, the selected word must match the current position. If there is no word matches the current position, simply go to next position. The BMM is similarly to the FMM, while the BMM goes backward from the end of the passage.
But the problem is that we can't guarantee a high accuracy, so that the performance of the search engine isn't very well. So, new strategies are brought in, such as semantic analysis, probability analysis and so on.
Here we just care about the strategy based on word library. A popular strategy is Minimum Word Fragment(MWF), that is, the one has the minimum total word fragment length among the segmentations of a passage is the best. The word fragment is defined to be the characters not matched.
Now you are invited to design an algorithm to implement the MWF strategy.
The first line of each test case contains two integers M and N. M is the number of words in the word library and N is the number of passages to be processed. (1 <= M <= 12500, 1 <= N <= 100 ) The next M lines is the word library, with each line containing one word; While the next N lines is the passage, with each line containing one passage. For similarity, the words and passages contain only English letters 'a' to 'z' (no spaces in it) . The length of each word in the word library is no more than 8, and the length of each passage is no more than 4k, namely 4096 bytes.
Process to the end of input.
For each test case, output a integer in the first line, which is the minimum total word fragment length. In the second line, output the corresponding segmentation. Use '#'s to separate words and word fragments. If there are multiple segmentations satisfy MWF, output anyone.
3 1 abc efg cdef abcdefg
In the sample above, there are two segmentations, which are "abc#d#efg" and "ab#cdef#g". In the first segmentation letter 'd' is not matched, so the total word fragment length is 1, while in the second segmentation the letters 'a','b','g' are not matched, so the total word fragment length is 3. We output the first segmentation according to MWF.
Author: CUI, Yanfeng
Source: ZOJ Monthly, July 2008