POJ 1580 - String Matching

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

概要

2つの文字列 word1, word2 に対して、類似度 appx を

appx(word1, word2) := (2 * common-letters(word1, word2))/(length(word1) + length(word2))

と定義する。 common-letters(word1, word2) は、word1 の連続する部分文字列であり、かつ word2 の連続する部分文字列であるような最長の文字列の長さである。

与えられた2つの文字列の appx を答える。

制約

• 書かれてないけど、2つの文字列の長さを \(N, M\) とすると \(O(MN)\) の解法で余裕で通った。

解法

word1, word2 のそれぞれをずらしつつ連続して一致する長さを数えるだけ。

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int gcd(int a, int b)
 6 {
 7   if (a < b) {
 8     swap(a, b);
 9   }
10   int r;
11   while ((r = a % b) != 0) {
12     a = b;
13     b = r;
14   }
15   return b;
16 }
17 
18 int main()
19 {
20   string s;
21   while (cin >> s && s != "-1") {
22     string t;
23     cin >> t;
24 
25     const int N = s.size(), M = t.size();
26     int ans = 0;
27     for (int i = 0; i < N; i++) {
28       int c = 0;
29       for (int j = 0; j < M && i+j < N; j++) {
30         if (s[i+j] == t[j]) {
31           ++c;
32         }
33       }
34       ans = max(ans, 2*c);
35     }
36     for (int j = 0; j < M; j++) {
37       int c = 0;
38       for (int i = 0; i < N && j+i < M; i++) {
39         if (s[i] == t[j+i]) {
40           ++c;
41         }
42       }
43       ans = max(ans, 2*c);
44     }
45 
46     int d = N + M;
47     cout << "appx(" << s << "," << t << ") = ";
48     if (ans == 0) {
49       cout << "0";
50     } else if (ans == d) {
51       cout << "1";
52     } else {
53       int g = gcd(ans, d);
54       ans /= g; d /= g;
55       cout << ans << "/" << d;
56     }
57     cout << endl;
58   }
59   return 0;
60 }