題目很簡單，給出一個字典，再給一些串，查詢這些串是否在字典中。
如果對字典排序后用二分查找，時間復雜度為O(N*logN)，由于題目沒有給出字典大小，這個界也不好估計。不過我用排序+二分TLE了。
下面是用Hash Table實現的算法，空間復雜度會高些（因為Hash表要很大的空間，來使得key分散開），但每次插入跟查詢的時間幾乎是O(1)，所以93ms就能AC。
1 #include <iostream>
2 #include <list>
3 #include <string>
4 #include <algorithm>
5
6 using namespace std;
7 const int maxn=50000;
8 struct node{
9 int idx;
10 node *next;
11 }htable[maxn];
12
13 //node *htable[maxn];
14 char dic[maxn][200];
15
16 unsigned long hash(char *key)
17 {
18 unsigned long h = 0;
19 while(*key)
20 {
21 h = (h << 4) + *key++;
22 unsigned long g = h & 0xf0000000L;
23 if(g)
24 h ^= g >> 24;
25 h &= ~g;
26 }
27 return h % maxn;
28 }
29
30 void insert(char *key,int idx)
31 {
32 unsigned long i=hash(key);
33 node *cur=htable[i].next;
34 node *pre=&htable[i];
35 while(cur!=NULL && strcmp(dic[cur->idx],key)!=0) {pre=cur;cur=cur->next;}
36 // 將新的key加入到hash table中
37 if(cur==NULL){
38 node *a=new node();
39 a->idx=idx;
40 a->next=NULL;
41 pre->next=a;
42 }
43 }
44
45 bool search(char *key)
46 {
47 unsigned long i=hash(key);
48 node *cur=htable[i].next;//,*pre=NULL;
49 while(cur!=NULL && strcmp(dic[cur->idx],key)!=0) {cur=cur->next;}
50 if(cur==NULL) return false;
51 return true;
52 }
53
54 int main()
55 {
56 //freopen("in.txt","r",stdin);
57 char s[200];
58 int i,j,k,n;
59 scanf("%d",&n);
60
61 // initialization
62 for(i=0;i<maxn;i++) htable[i].next=NULL;
63 // 插入數據
64 for(i=0;i<n;i++){
65 getchar();
66 scanf("%s",s);
67 strcpy(dic[i],s);
68 insert(s,i);
69 }
70
71 scanf("%d",&n);
72 for(i=0;i<n;i++){
73 int flag=0;
74 while(true){
75 scanf("%s",s);
76 if(strcmp(s,"-1")==0) break;
77 if(!search(s)){
78 if(flag==0){
79 printf("Email %d is not spelled correctly.\n",i+1);
80 flag=1;
81 }
82 printf("%s\n",s);
83 }
84 }
85 if(flag==0) printf("Email %d is spelled correctly.\n",i+1);
86 }
87 printf("End of Output\n");
88 return 1;
89 }
這是超時的版本，用了list的STL跟binary_search函數來查找。但超時可能是因為用C++的STL和輸入輸出，因為Discuss中有人用快排+二分過的。
1 list<string> dic;//=new list<string>(51000);
2 char tmp[200];
3 int main()
4 {
5 int i,j,k,n;
6 string s;
7 scanf("%d",&n);
8 for(i=0;i<n;i++) {getchar();scanf("%s",tmp);dic.push_back(new string(tmp));}
9 //dic.insert("anc");
10 //sort(dic.begin(),dic.end());
11 dic.sort();
12 for(list<string>::iterator it=dic.begin();it!=dic.end();it++) cout<<(*it)<<endl;
13 scanf("%d",&n);
14 for(i=0;i<n;i++){
15 int flag=1;
16 while(cin>>s && s!="-1"){
17 if(!binary_search(dic.begin(),dic.end(),s)){
18 if(flag==1){
19 printf("Email %d is not spelled correctly.\n",i+1);
20 flag=0;
21 }
22 cout<<s<<endl;
23 }
24 }
25 if(flag==1) printf("Email %d is spelled correctly.\n",i+1);
26 }
27 printf("End of Output\n");
28 return 1;
29 }