题解 | 实现字通配符*

#include <iostream>
#include <vector>

using namespace std;

bool GetMatchLen(const char* p, char* s, int len, vector<int>& valid) {
    if (*p == '\0') {
        if ( len > 0 ) {
            valid.push_back(len);
            return true;
        } else {
            return false;
        }
    }
    if (*s == '\0') {
        return false;
    }
    if (*p == '*') {
        auto ok = false;
        if (GetMatchLen(p + 1, s, len, valid)) {
            ok = true;
        }
        if (GetMatchLen(p, s + 1, len + 1, valid) ||
                GetMatchLen(p + 1, s + 1, len + 1, valid))  {
            ok = true;
        }
        return ok;
    }
    if (*p != *s) {
        return false;
    } else {
        return GetMatchLen(p + 1, s + 1, len + 1, valid);
    }
}


int main() {
    string p, s;
    cin >> p >> s;

    // 合并连续的 '*'
    string np;
    bool last_star = false;
    for (char c : p) {
        if (c == '*') {
            if (!last_star) {
                np += '*';
                last_star = true;
            }
        } else {
            np += c;
            last_star = false;
        }
    }
    p = np;

     // 如果模式全是 '*'
     int n = s.size();
    bool all_star = true;
    for (char c : p) if (c != '*') { all_star = false; break; }
    if (all_star) {
        vector<pair<int,int>> ans;
        for (int l = 0; l < n; ++l) {
            for (int len = 1; l + len - 1 < n; ++len) {
                ans.emplace_back(l, len);
            }
        }
        if (ans.empty()) cout << "-1 0\n";
        else {
            for (auto &pr : ans) cout << pr.first << ' ' << pr.second << '\n';
        }
        return;
    }

    int num = 0;
    for(auto i = 0; i < s.size(); i++) {
        vector<int> valid;
        GetMatchLen(p.c_str(), &s[i], 0, valid);
        for(auto v : valid) {
            cout << i << " " << v << endl;
        }
        num += valid.size();
    }
    if(num == 0) {
        cout << "-1 0" <<endl;
    }
}