1 条题解
-
0
#include <iostream> #include <string> #include <algorithm> using namespace std; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int overlap(const string& a, const string& b) { int max_common = 0; int len_a = a.size(), len_b = b.size(); for (int offset = -len_b + 1; offset < len_a; ++offset) { int common = 0; for (int i = 0; i < len_b; ++i) { int j = offset + i; if (j >= 0 && j < len_a && a[j] == b[i]) { ++common; } } if (common > max_common) max_common = common; } return max_common; } int main() { string a, b; while (cin >> a) { if (a == "-1") break; cin >> b; int common = overlap(a, b); int numerator = common * 2; int denominator = a.size() + b.size(); cout << "appx(" << a << "," << b << ") = "; if (numerator == 0) cout << "0" << endl; else if (numerator == denominator) cout << "1" << endl; else { int g = gcd(numerator, denominator); cout << (numerator / g) << "/" << (denominator / g) << endl; } } return 0; }
- 1
信息
- ID
- 581
- 时间
- 1000ms
- 内存
- 10MiB
- 难度
- 7
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者