POJ 3852 - String LD

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

概要

n 個の小文字のアルファベットからなる文字列が与えられる．

1ステップですべての文字列から先頭の文字を取り除くという操作を行う． この操作を

• ある文字列が空になる
• 重複した文字列が表れる

のいずれかの条件を満たすまで繰り返したとき，そのステップ数を答える．

制約

• 1 <= n <= 100
• 文字列の長さ <= 100

解法

最短の文字列の長さを m とすると，長さが m より大きい文字列は考慮に入れなくてよい．

長さが m の文字列を各ペアについて，後ろから何文字分マッチするかを調べ上げてその最小値 x を求めれば，m-1-x が答えである．

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct by_size
 7 {
 8   bool operator()(const string& l, const string& r) const
 9   {
10     if (l.size() == r.size()) {
11       return l < r;
12     } else {
13       return l.size() < r.size();
14     }
15   }
16 };
17 
18 int match(const string& s, const string& t)
19 {
20   int c = 0;
21   for (string::const_iterator it = s.begin(), jt = t.begin();
22       it != s.end() && jt != t.end() && *it == *jt;
23       ++it, ++jt, ++c);
24   return c;
25 }
26 
27 int main()
28 {
29   ios::sync_with_stdio(false);
30   int N;
31   while (cin >> N && N != 0) {
32     vector<string> v(N);
33     for (int i = 0; i < N; i++) {
34       cin >> v[i];
35       reverse(v[i].begin(), v[i].end());
36     }
37     sort(v.begin(), v.end(), by_size());
38 
39     vector<string>::const_iterator last = v.begin();
40     while (last != v.end() && last->size() == v[0].size()) {
41       ++last;
42     }
43     const int len = v[0].size();
44     int ans = len-1;
45     for (vector<string>::const_iterator it = v.begin(); it != last; ++it) {
46       for (vector<string>::const_iterator jt = it+1; jt != last; ++jt) {
47         ans = min(ans, len-1-match(*it, *jt));
48       }
49     }
50     cout << ans << endl;
51   }
52   return 0;
53 }