1 条题解

  • 0
    @ 2025-5-26 21:24:12
    #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
    上传者