Posted on 2008-04-23 22:19
superman 閱讀(250)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1170 C++ 00:00.01 840K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 int gcd(int a, int b)
8 {
9 if(b == 0)
10 return a;
11 return gcd(b, a % b);
12 }
13
14 int main()
15 {
16 string s1, s2;
17 while(cin >> s1 >> s2)
18 {
19 cout << "appx" << '(' << s1 << ',' << s2 << ')' << " = ";
20
21 if(s1 == s2)
22 {
23 cout << 1 << endl;
24 continue;
25 }
26
27 int max = 0;
28 for(int i = 0; i < s1.size(); i++)
29 {
30 int sum = 0;
31 for(int j = 0; j < s2.size(); j++)
32 if(i + j >= s1.size())
33 break;
34 else
35 sum += (s1[i + j] == s2[j]);
36 max >?= sum;
37 }
38 for(int i = 0; i < s2.size(); i++)
39 {
40 int sum = 0;
41 for(int j = 0; j < s1.size(); j++)
42 if(i + j >= s2.size())
43 break;
44 else
45 sum += (s2[i + j] == s1[j]);
46 max >?= sum;
47 }
48
49 max *= 2;
50 int len = s1.size() + s2.size();
51
52 while(true)
53 {
54 int x = gcd(max, len);
55 if(x == 1)
56 break;
57 max /= x, len /= x;
58 }
59
60 if(max == 0)
61 cout << 0 << endl;
62 else
63 cout << max << '/' << len << endl;
64 }
65
66 return 0;
67 }
68