题目描述
Well, how do you feel about mobile phone? Your answer would probably be something like that “It’s so convenient and benefits people a lot”. However , if you ask Merlin this question on the New Year’s Eve , he will definitely answer “ What a trouble! I have to keep my fingers moving on the phone the whole night , because I have so many greeting messages to send !” . Yes , Merlin has such a long name list of his friends , and he would like to send a greeting message to each of them . What’s worse , Merlin has another long name list of senders that have sent message to him , and he doesn’t want to send another message to bother them ( Merlin is so polite that he always replies each message he receives immediately ). So , before he begins to send messages , he needs to figure to how many friends are left to be sent . Please write a program to help him.Here is something that you should note. First , Merlin’s friend list is not ordered , and each name is alphabetic strings andcase insensitive . These names are guaranteed to be not duplicated . Second, some senders may send more than one message to Merlin , therefore the sender list may be duplicated . Third , Merlin is known by so many people , that’s why some message senders are even not included in his friend list.
输入
There are multiple test cases . In each case , at the first line there are two numbers n and m ( 1<=n , m<=20000) , which is the number of friends and the number of messages he has received . And then there are n lines of alphabetic strings ( the length of each will be less than 10 ) , indicating the names of Merlin’s friends , one pre line . After that there are m lines of alphabetic string s ,which are the names of message senders .The input is terminated by n=0.
输出
For each case , print one integer in one line which indicates the number of left friends he must send .
样例输入
53InkfishHenryCarpMaxJerichoCarpMaxCarp0
样例输出
3
题目来源
第九届中山大学程序设计竞赛预选题
题目链接：?&method=showdetail&id=1121
题目大意：一个人要传消息给他的n个朋友，其中已经有m个（可能重复）收到了，问这个人还要发多少消息
题目分析：如果用trie树做注意红色标出的意思是不分大小写，，建立26叉字典树，基本建树插入，ans初始化为n，查找的时候找到一个将其从字典中删除即可，用set + string做比较费时，但是代码很好写，很好理解
Trie树：
#include <cstdio>#include <cstring>char s[11];int cnt, ans;int change(char ch){if(ch <= 'Z' && ch >= 'A')return ch – 'A';if(ch <= 'z' && ch >= 'a')return ch – 'a'; }struct node{node *next[26];bool end;node(){memset(next, 0, sizeof(next));end = false;}};void Insert(node *p, char *s){for(int i = 0; s[i] != '\0'; i++){int idx = change(s[i]);if(p -> next[idx] == NULL)p -> next[idx] = new node();p = p -> next[idx];}p -> end = true;}void Search(node *p, char *s){int i;for(i = 0; s[i] != '\0'; i++){int idx = change(s[i]);if(p -> next[idx] == NULL)return;p = p -> next[idx];}if(p -> end){ans –;p -> end = false;}}int main(){int n, m;while(scanf("%d", &n) && n){ans = n;node *root = new node();scanf("%d", &m);for(int i = 0; i < n; i++){scanf("%s", s);Insert(root, s);}for(int i = 0; i < m; i++){scanf("%s", s);Search(root, s);}printf("%d\n", ans);}}
set + string：
#include <cstdio>#include <string>#include <iostream>#include <set>using namespace std;int main(){int n, m;string str;while(scanf("%d %d", &n, &m) != EOF && n){set <string> s;for(int i = 0; i < n; i++){cin >> str;for(int j = 0; j < str.length(); j++)str[j] = toupper(str[j]);s.insert(str);}for(int i = 0; i < m; i++){cin >> str;for(int j = 0; j < str.length(); j++)str[j] = toupper(str[j]);set <string> :: iterator it = s.find(str);if(it != s.end())s.erase(str);}cout << s.size() << endl;}}
在繁华中体会热闹;若是厌倦了喧嚣，寻一处宁静的幽谷，
