这次先写思路。最后贴题目。算法描述以后在写

本次题目的大意是：

1. BBS某版上只有两种人：说谎者与诚实者
2. 版上所有人互相指控
3. 例：Alice指控Bob。从这条指控可以知道Alice和Bob中有且仅有一个说谎者，另一个必然是诚实者，但无法判断谁是说谎者。
4. 说谎者必说谎，诚实者必诚实
5. 要求编写程序输出说谎者和诚实者的人数（分离说谎者和诚实者即可，不要求指出某人是否是说谎者）

Liar, Liar

As a newbie on a particular internet discussion board, you notice a distinct trend among its veteran members; everyone seems to be either unfailingly honest or compulsively deceptive. You decide to try to identify the members of the two groups, starting with the assumption that every senior member either never lies or never tells the truth. You compile as much data as possible, asking each person for a list of which people are liars. Since the people you are asking have been around on the board for a long time, you may assume that they have perfect knowledge of who is trustworthy and who is not. Each person will respond with a list of people that they accuse of being liars. Everyone on the board can see that you are a tremendous n00b, so they will grudgingly give you only partial lists of who the liars are. Of course these lists are not to be taken at face value because of all the lying going on.

You must write a program to determine, given all the information you’ve collected from the discussion board members, which members have the same attitude toward telling the truth. It’s a pretty popular discussion board, so your program will need to be able to process a large amount of data quickly and efficiently.

Input Specifications

Your program must take a single command line argument; the name of a file. It must then open the file and read out the input data. The data begins with the number of veteran members n followed by a newline. It continues with n chunks of information, each defining the accusations made by a single member. Each chunk is formatted as follows:

<accuser name> <m>

followed by m lines each containing the name of one member that the accuser says is a liar. accuser name and m are separated by some number of tabs and spaces. m will always be in [0, n]. All member names contain only alphabetic characters and are unique and case-sensitive.

Example input file:

5
Stephen   1
Tommaso
Tommaso   1
Galileo
Isaac     1
Tommaso
Galileo   1
Tommaso
George    2
Isaac
Stephen

Output Specifications

Your output must consist of two numbers separated by a single space and followed by a newline, printed to standard out. The first number is the size of the larger group between the liars and the non-liars. The second number is the size of the smaller group. You are guaranteed that exactly one correct solution exists for all test data.

Example output:

Breathalyzer

To safeguard against the dreaded phenomenon of wall posting while drunk, Facebook is implementing a feature that detects when post content is too garbled to have been done while sober and informs the user that they need to take an online breathalyzer test before being allowed to post.

废话，不翻译。

Unfortunately, there is far too much content for a given set of persons to evaluate by hand. Fortunately, you are a programmer of some repute and can write a program that processes and evaluates wall posts. You realize that such a program would be of great use to society and intend to resolve the problem once and for all. The program you write must compute a score for a body of text, returning this score upon completion.

废话，不翻译。

Your program will be given a list of accepted words and run on one wall post at a time. For each word W in the post, you must find word W’ from the list of accepted words such that the number of changes from W to W’ is minimized. It is possible that W is already W’ and thus the number of changes necessary is zero. A change is defined as replacing a single letter with another letter, adding a letter in any position, or removing a letter from any position. The total score for the wall post is the minimum number of changes necessary to make all words in the post acceptable.

题目提供了一个单词表(从这里下载) 。对于待分析字符串中的每个词，你的程序要从单词表中找到最接近的词并计算这两个词的“距离”。两个字符串的“距离”定义为从字符串1变成字符串2所需要的最小操作数，允许的操作包括：

1. 将一个字母替换为另一个字母
2. 删除一个字母
3. 插入一个字母

Input Specification

Your program must take a single string argument, representing the file name containing the wall post to analyze. In addition, your program must open up and read the accepted word list from the following static path location:

/var/tmp/twl06.txt

你的程序的参数为： 单词表文件 待分析文本文件

For testing purposes, you may download and examine the accepted word list here. When submitting your code, you do not need to include this file, as it is already present on the machine.

The input file consists entirely of lower case letters and space characters. You are guaranteed that the input file will start with a lower case letter, and that all words are separated by at least one space character. The file may or may not end with a new line character.

Example input file:

tihs sententcnes iss nout varrry goud

You are guaranteed that your program will run against well formed input files and that the accepted word list is identical to the one provided for testing.

Output Specification

Your program must print out the minimum number of changes necessary to turn all words in the input wall post into accepted words as defined by the word list file. Words may not be joined together, or separated into multiple words. A change in a word is defined as one of the following:

1. Replacing any single letter with another letter.
2. Adding a single letter in any position.
3. Removing any single letter.

1. 替换一个字母
2. 添加一个字母
3. 删除一个字母

This score must be printed out as an integer and followed by a single new line.

Example Output (newline after number):

8