> //============================================================================
> // Name        : main1035.cpp
> // Author      : 
> // Version     :
> // Copyright   : Your copyright notice
> // Description : Hello World in C++, Ansi-style
> //============================================================================
> 
> #include <iostream>
> #include <string>
> #include <vector>
> using namespace std;
> 
> int cnt = 1;
> string dict[10001];
> 
> int partion(vector<int>& array, int p, int r) {
> 		int x = array[r];
> 		int i = p - 1;//注意这点，把i设成负值，然后作为移动的标志
> 		int j;
> 		for (j = p; j < r; j++) {
> 			if (array[j] < x) {
> 				i++;
> 				int temp = array[j];
> 				array[j] = array[i];
> 				array[i] = temp;
> 			}
> 		}
> 		int temp = array[j];
> 		array[j] = array[i + 1];
> 		array[i + 1] = temp;
> 		return i+1;//返回的应该是交换后的哨兵的位置
> }
> 		//递归解决每个划分后的小
> void quickSort(vector<int>& array, int p, int r) {
> 		if (p < r) {
> 			int q = partion(array, p, r);
> 			quickSort(array, p, q - 1);
> 			quickSort(array, q + 1, r);
> 		}
> }
> 
> class node{
> 	public:
> 	node* sub[27];
> 	int num;
> 	node(){
> 		num = 0;
> 		//cnt++;
> 		for(int i = 0; i < 27; i++) sub[i] = NULL;
> 	}
> };
> node* root;
> void buildTree(){
> 	root = new node();
> 	string s;
> 	while(getline(cin, s)){
> 		if(s == "#") return;
> 		dict[cnt] = s;
> 		node *iter = root;
> 		int len = s.length();
> 		for(int i = 0; i < len; i++){
> 			node *next = iter->sub[s[i] - 'a'];
> 			if(next == NULL){
> 				node *temp = new node();
> 				iter->sub[s[i] - 'a'] = temp;
> 				iter = iter->sub[s[i] - 'a'];
> 			}
> 			else{
> 				iter = next;
> 			}
> 			//if(s == "award")
> 		}
> 		node *newN = new node();
> 		iter->sub[26] = newN;
> 		iter = iter->sub[26];
> 		iter->num = cnt;
> 		cnt++;
> 	}
> }
> 
> int have(node* start, string suffix){
> 	node *iter = start;
> 	int len = suffix.length();
> 
> 	//int prc = len;
> 	for(int i = 0; i < len; i++){
> 		//cout << (int)(suffix[i]-'a') << endl;
> 		if(iter->sub[suffix[i]-'a'] == NULL){
> 			return 0;
> 		}
> 		//cout << 233 << endl;
> 		iter = iter->sub[suffix[i] - 'a'];
> 	}
> 
> 	if(iter->sub[26] == NULL) return 0;
> 	return iter->sub[26]->num;
> }
> 
> int main() {
> 
> 	string ss = "test";
> 	//cout << "q" + ss.substr(4);
> 	buildTree();
> 	//cout << root << endl;
> 	string s;
> 	while(getline(cin, s)){
> 		if(s == "#") return 0;
> 		if(have(root, s) > 0){
> 			//cout << have(root, s) << endl;
> 			cout << s << " is correct\n";
> 			continue;
> 		}
> 		vector<int> res;
> 		int len = s.length();
> 		//int cnt = 0;
> 		//下面开始考虑增加一个
> 		node *iter = root;
> 		for(int i = 0; i <= len; i++){
> 			string sfx = s.substr(i);
> 			//cout << iter << endl;
> 			for(char c = 'a'; c <= 'z'; c++){
> 				//cout << c + sfx << endl;
> 				//cout << iter << endl;
> 				int result = have(iter, c + sfx);
> 				//cout << i << " " << c << endl;
> 				if(result > 0) res.push_back(result);
> 				//cout << result << endl;
> 
> 			}
> 			if(i != len) iter = iter->sub[s[i] - 'a'];
> 			if(iter == NULL) break;
> 		}
> 		//cout << 1 << endl;
> 		//替换一个
> 		iter = root;
> 		for(int i = 0; i < len; i++){
> 			string sfx = s.substr(i+1);
> 			for(char c = 'a'; c <= 'z'; c++){
> 				int result = have(iter, c + sfx);
> 				if(result > 0) res.push_back(result);
> 			}
> 			iter = iter->sub[s[i] - 'a'];
> 			if(iter == NULL) break;
> 		}
> 		//删掉一个
> 		if(len > 1){
> 			iter = root;
> 			for(int i = 0; i < len; i++){
> 				string sfx = s.substr(i+1);
> 				int result = have(iter, sfx);
> 				if(result > 0) res.push_back(result);
> 				iter = iter->sub[s[i] - 'a'];
> 				if(iter == NULL) break;
> 			}
> 
> 		}
> 
> 		if(res.empty()){
> 			cout << s << ":" << endl;
> 			continue;
> 		}
> 		int sz = res.size();
> 		quickSort(res, 0, sz-1);
> 		cout << s << ":";
> 		int idx = 0;
> 		for(int i = 0; i < sz; i++) {
> 			if(res[i] == idx) continue;//这个不能少，否则重复输出！！！
> 			idx = res[i];
> 			cout << " " << dict[res[i]];
> 		}
> 		cout << endl;
> 
> 	}
> 	//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
> 	return 0;
> }