POJ 2797 最短前缀（贪心算法）

carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate

carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<deque>
#include<fstream>
#include<iomanip>
#include<map>
#include<queue>
#include<string>
#include<set>
#include<stack>
#include<vector>
typedef long long ll;
using namespace std;
char str[1002][22];
int strl[1002];
char ten[22];

int main()
{
	int count=0;
	while((scanf("%s",&str[count]))!=EOF)
	{
		strl[count]=strlen(str[count]);

		count++;
	}
	/*for(int i=0;i<count;i++)
	{
		cout<<strl[i]<<endl;
	}*/
	int i,j,k;
	for(i=0;i<count;i++)//挨个查找每个单词的唯一前缀
	{
		for(j=1;j<=strl[i];j++)//!!!!!!!!!!
		//挨个查找该字符串的前缀是否唯一标识，注意子串长度从1开始，空串不是子串
		{
			memset(ten,0,sizeof(ten));
			for(k=0;k<j;k++)
			{
				ten[k]=str[i][k];
			}
			ten[k]='\0';//使用ten数组暂时保存要判断是否唯一的子串
			for(k=0;k<count;k++)
			{
				if(k!=i)//判断子串是否是其他字符串的字符串
				{
					if(strstr(str[k],ten)==str[k])
					    break;
				}
			}
			if(k==count){//如果不是，打印，跳出循环找下一个串的表一最短前缀
				cout<<str[i]<<" "<<ten<<endl;
				break;
			}
		}
		if(j==strl[i]+1) cout<<str[i]<<" "<<str[i]<<endl;
		//如果字符串本身也是其他串的子串则打印该串本身
	}
	return 0;
		
}