动态规划 —— 求解通配符问题（wildcard）

he?p
- help, heap, √
- hellp, ×
*p*（必须包含 p，左右随意）
- help, papa， √
- hello ×
*bb*（必须包含连续的两个 bb，左右随意）
- babbc √

1. 穷举法的处理

? 的匹配处理其实很好处理，困难的地方还在于 * 的匹配问题。

假定给定的范式包含 m 个“*”，每次出现“*”就分割 1 次范式。那么，“此范式是否对应字符串”的问题可分为 m+1 个子问题。例如，范式t*l?*o*r?ng*s可分为{t*, l?*, o*, r?ng*, s}。那么当给出字符串thelordoftherings时，为了找出字符串中的前几个对应第一个分割快，穷举搜索法会尝试所有可能的组合。找出对应于第一个分割快的 3 （本例为前 3 ）个字符后，利用递归调用就能很容易地判断出剩下的字符串lordoftings是否对应于剩余的 4 个分割快。

bool match(const string& w, const string& s){

    int pos = 0;

    while (pos < w.size() && pos < s.size() && (w[pos] == '?' || w[pos] == s[pos]))

        ++pos;

    if (pos == w.size())

        return pos == s.size();

    if (w[pos] == '*'){

        for (int skip = 0; pos + skip <= s.size(); ++skip){

            if (match(w.substr(pos+1), s.substr(pos+skip)))

                return true;

                                    // pos + skip <= s.size()

                                    // 匹配全部

        }

        return false;

    }

}

巴特西

动态规划 —— 求解通配符问题（wildcard）

1. 穷举法的处理

最新文章

热门文章