百練 2797 最短前綴 解題報告

1.Link:http://poj.grids.cn/practice/2797/

2.Content

總時間限制:

1000ms

內存限制:

65536kB

描述

一個字符串的前綴是從該字符串的第一個字符起始的一個子串。例如 "carbon"的字串是: "c", "ca", "car", "carb", "carbo", 和 "carbon"。注意到這裡我們不認為空串是字串, 但是每個非空串是它自身的字串. 我們現在希望能用前綴來縮略的表示單詞。例如, "carbohydrate" 通常用"carb"來縮略表示. 現在給你一組單詞, 要求你找到唯一標識每個單詞的最短前綴
在下面的例子中，"carbohydrate" 能被縮略成"carboh", 但是不能被縮略成"carbo" (或其余更短的前綴) 因為已經有一個單詞用"carbo"開始
一個精確匹配會覆蓋一個前綴匹配，例如，前綴"car"精確匹配單詞"car". 因此 "car" 是 "car"的縮略語是沒有二義性的 , “car”不會被當成"carriage"或者任何在列表中以"car"開始的單詞.

輸入

輸入包括至少2行，至多1000行. 每行包括一個以小寫字母組成的單詞，單詞長度至少是1，至多是20.

輸出

輸出的行數與輸入的行數相同。每行輸出由相應行輸入的單詞開始，後面跟著一個空格接下來是相應單詞的沒有二義性的最短前綴標識符。

樣例輸入

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

3.Code

 #include <iostream>
 #include <cstdlib>
 #include <cstdio>
 #include <cstring>
  MAXSTR 21
  MAXNUM 1010
 
         count =           (scanf(,arr[count]) != EOF) count++     
               (i = ; i < count; i++          len =         (j = ;j < len; j++               chs[j] =              
             (k = ; k < count; k++                   chs2[j] =                  (!strcmp(chs,chs2) && k!=i)               
             (k >= count)           (j == len) printf(          printf(        }

4.Method

（1）暴力查找

（2）判斷前綴不能使用strstr