#include <iostream>
#include <map>
#include <algorithm>
#include <string>
using namespace std;

const MAX = 1000;

string words[MAX];
string ordered[MAX];
map<string, string> prefix;

int diffrentPlace(string s1, string s2){ //s1 < s2
	for(int i = 0; i < s1.size(); i++) 
		if(s1[i] != s2[i])
			return i;
	return i - 1;
}

int main(){
	int i, num = 0;
	while(cin>>words[num]){
		ordered[num] = words[num];
		num++;
	}
	sort(ordered, ordered + num);

	int same1 = diffrentPlace(ordered[0], ordered[1]);
	int same2 = diffrentPlace(ordered[0], ordered[1]);
	prefix[ordered[0]] = ordered[0].substr(0, same1 + 1);
	for(i = 1; i < num - 1; i++){
		if(same1 == ordered[i-1].size() - 1)
			same1++;
		same2 = diffrentPlace(ordered[i], ordered[i+1]);
		prefix[ordered[i]] = ordered[i].substr(0, 1 + (same1 > same2 ? same1 : same2));
		same1 = same2;
	}
	if(ordered[i - 1].size() - 1 == same2)
		same2++;
	prefix[ordered[i]] = ordered[i].substr(0, same2 + 1);

	for(i = 0; i < num; i++)
		cout<<words[i]<<' '<<prefix[words[i]]<<endl;
	return 0;
}

• Re:谁能告诉我这个程序为什么错了 (13) chengmingvictor 2005-08-01 11:37:02
  • Re:这是我写的这个算法的加强版，哪位兄弟能告诉我错在哪里啊 (1488) yangjie 2006-03-19 09:53:34