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

总时间:

1000ms

内存:

65536kB描述

⼀个字符串的前缀是从该字符串的第⼀个字符起始的⼀个⼦串。例如 \"carbon\"的字串是: \"c\和 \"carbon\"。注意到这⾥我们不认为空串是字串, 但是每个⾮空串是它⾃⾝的字串. 我们现在希望能⽤前缀来缩略的表⽰单词。例如, \"carbohydrate\"通常⽤\"carb\"来缩略表⽰. 现在给你⼀组单词, 要求你找到唯⼀标识每个单词的最短前缀

在下⾯的例⼦中，\"carbohydrate\" 能被缩略成\"carboh\但是不能被缩略成\"carbo\" (或其余更短的前缀) 因为已经有⼀个单词⽤\"carbo\"开始

⼀个精确匹配会覆盖⼀个前缀匹配，例如，前缀\"car\"精确匹配单词\"car\". 因此 \"car\" 是 \"car\"的缩略语是没有⼆义性的 , “car”不会被当成\"carriage\"或者任何在列表中以\"car\"开始的单词.输⼊

输⼊包括⾄少2⾏，⾄多1000⾏. 每⾏包括⼀个以⼩写字母组成的单词，单词长度⾄少是1，⾄多是20.输出

输出的⾏数与输⼊的⾏数相同。每⾏输出由相应⾏输⼊的单词开始，后⾯跟着⼀个空格接下来是相应单词的没有⼆义性的最短前缀标识符。样例输⼊

carbohydratecart

carburetorcaramelcariboucarboniccartilagecarboncarriagecartoncar

carbonate

样例输出

carbohydrate carbohcart cart

carburetor carbucaramel caracaribou cari

carbonic carbonicartilage carticarbon carboncarriage carrcarton cartocar car

carbonate carbona

来源

翻译⾃Rocky Mountain 2004

1 #include 2 #include

3 using namespace std; 4 string s[1005]; 5 int main() 6 {

7 int n=0;

8 while(cin>>s[++n]);//输⼊完以后 先按回车，再按\"CTRL+Z\"，再按回车 9 for(int i=1; i<=n; ++i)//从第1个字符串数组开始10 {

11 for(int j=1; j<=s[i].size(); ++j)//长度从1到s[i]的最⼤长度12 {

13 //substr功能是复制⼦字符串,要求从指定位置开始，并具有指定的长度14 //substr(指定位置，指定的长度)

15 string ss=s[i].substr(0,j);16 int flag=1;

17 for(int k=1; k<=n; ++k)//从第1个字符串数组开始，⼀⼀⽐较18 {

19 if(k!=i&&s[k].substr(0,j)==ss)//如果有别的字符串数组的前缀和这个相等，则失败20 {

21 flag=0;22 break;23 }24 }

25 if(flag||j==s[i].size())//满⾜条件输出26 {

27 cout<