POJ 2001 - Shortest Prefixes

http://poj.org/problem?id=2001

概要

\(N\) 個の単語が与えられる． 各単語について，その単語が \(N\) 個の単語の中でユニークになるような最短の prefix を答える．

制約

• \(1 \le N \le 1000\)
• 各単語は1文字以上20文字以下小文字のアルファベットのみからなる

解法

各単語の全 prefix を map に入れてカウントしてから，各単語について個数が1の最も短い prefix を答えればよい． キーを std::string にしても間に合いそうだったが，念のため固定長の文字列でやった．

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <map>
 4 using namespace std;
 5 
 6 struct fixed_string
 7 {
 8   char s[25];
 9   fixed_string(const char *t) { strcpy(s, t); }
10   fixed_string(const fixed_string& t) { strcpy(s, t.s); }
11   bool operator<(const fixed_string& t) const { return strcmp(s, t.s) < 0; }
12 };
13 
14 int main()
15 {
16   map<fixed_string, int> m;
17   static char a[1000][25];
18   int N = 0;
19   while (scanf("%s", a[N]) != EOF) {
20     for (int i = 1; a[N][i-1] != '\0'; i++) {
21       char c = a[N][i];
22       a[N][i] = '\0';
23       fixed_string fs(a[N]);
24       ++m[fs];
25       a[N][i] = c;
26     }
27     N++;
28   }
29 
30   for (int i = 0; i < N; i++) {
31     fixed_string fs(a[i]);
32     int j = 1;
33     for (; a[i][j] != '\0'; j++) {
34       char c = fs.s[j];
35       fs.s[j] = '\0';
36       if (m[fs] > 1) {
37         fs.s[j] = c;
38       } else {
39         break;
40       }
41     }
42     printf("%s %s\n", a[i], fs.s);
43   }
44   return 0;
45 }