2013
11-12

# Cow Phrasebook

Ever the innovator, Farmer John is teaching cows to speak some phrases in human language. He writes each new phrase the cows learn in his phrase book, a total of M (1 <= M <= 1,000) so far.

When Farmer John is on a vacation, he can only communicate with his cows by telephone. Being an active vacationer, FJ visits beaches and fine restaurants when away from the farm. When he returns, his answering machine is full of N (1 <= N <= 10,000) messages, many potentially from the cows.

FJ vacations frugally and thus gets poor telephone service. Many of the recorded messages cut off before they are complete. Help FJ determine whether the recorded messages are from the phrasebook by determining if the message begins a phrase.

You will be given the phrasebook and a set of texts of the recorded messages. Count the number of recorded messages that are the beginning (prefix) of a phrase from the phrase book.

Complete phrases are from 1 to 60 characters in length, each of which is either a letter (upper or lower case), a period (.), comma (,), question mark (?) or space. There are no leading spaces, trailing spaces, or double spaces in a phrase. Comparisons are case-sensitive, and a phrase is in fact, considered to be prefix of itself.

Line 1: Two space-separated integers, M and N

Lines 2..M+1: Phrases from the phrase book, one per line.

Lines M+2..M+N+1: Phrases spoken by cows, one per line.

Line 1: A single integer that is the count of the number of messages that were proper prefixes of the phrasebook.

3 4
I will not buy this record, it is scratched.
My hovercraft is full of eels.
Do you want to come back to my place? Bouncy, bouncy.
I will not buy this rec
My helicopter is
Do you want to come back
I will not buy this cat.

2

Explanation of the sample:

Three input phrases (record, eels, bouncy); four query phrases (buy, helicopter, come back, cat).

The messages ‘I will not buy this rec’ and ‘Do you want to come back’ are valid prefixes of the phrasebook.

//* @author: Yeming Hu"[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */"
import java.util.*;

public class Main
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
String mn = sc.nextLine();
Scanner lmn = new Scanner(mn);
int m = lmn.nextInt();
int n = lmn.nextInt();
String[] phrases = new String[m];
for(int i = 0; i < m; i++)
{
phrases[i] = sc.nextLine();
}
Arrays.sort(phrases);
int result = 0;
for(int i = 0; i < n; i++)
{
String line = sc.nextLine();
int index = Arrays.binarySearch(phrases,line);
if(index >= 0)
{
result++;
}else
{
index = -1 * index - 1;
if(index == m)
{
continue;
}
if(phrases[index].startsWith(line))
{
result++;
}
}
}
System.out.println(result);
}
}

1. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测