题解 | #实现字通配符*#

解题思路

这是一道关于通配符匹配的问题，主要思路如下：

1. 使用DFS（深度优先搜索）来实现通配符'*'的匹配
2. ''可以匹配0个或多个字符，因此在遇到''时有三种选择：
   • 不匹配任何字符，继续匹配下一个模式字符
   • 匹配当前字符，保持在当前模式字符
   • 匹配当前字符，继续匹配下一个模式字符
3. 使用 set 来存储所有匹配成功的结束位置
4. 对于每个可能的起始位置，尝试进行匹配

代码

#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;

string p, t;  // p为模式串，t为目标串
set<int> st;  // 存储匹配成功的结束位置

void dfs(int i, int j) {
    // 模式串匹配完成
    if (j == p.size()) {
        st.insert(i);
        return;
    }
    // 目标串到达末尾
    if (i == t.size()) return;
    
    // 字符匹配或遇到通配符
    if (t[i] == p[j]) {
        dfs(i + 1, j + 1);
    }
    else if (p[j] == '*') {
        dfs(i, j + 1);     // 不匹配任何字符
        dfs(i + 1, j);     // 匹配当前字符，保持在*
        dfs(i + 1, j + 1); // 匹配当前字符，移动到下一个
    }
}

void solve() {
    bool flag = false;
    // 尝试每个可能的起始位置
    for (int i = 0; i < t.size(); ++i) {
        if (t[i] == p[0] || p[0] == '*') {
            dfs(i, 0);
            if (!st.empty()) {
                flag = true;
                for (auto it = st.begin(); it != st.end(); ++it) {
                    if (*it - i) cout << i << " " << *it - i << endl;
                }
            }
            st.clear();
        }
    }
    if (!flag) cout << "-1 0" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> p >> t;
    solve();
    return 0;
}

import java.util.*;

public class Main {
    static String p, t;
    static TreeSet<Integer> st;
    static boolean flag;
    
    static void dfs(int i, int j) {
        if (j == p.length()) {
            st.add(i);
            return;
        }
        if (i == t.length()) return;
        
        if (t.charAt(i) == p.charAt(j)) {
            dfs(i + 1, j + 1);
        }
        else if (p.charAt(j) == '*') {
            dfs(i, j + 1);
            dfs(i + 1, j);
            dfs(i + 1, j + 1);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        p = sc.next();
        t = sc.next();
        st = new TreeSet<>();
        flag = false;
        
        for (int i = 0; i < t.length(); ++i) {
            if (t.charAt(i) == p.charAt(0) || p.charAt(0) == '*') {
                dfs(i, 0);
                if (!st.isEmpty()) {
                    flag = true;
                    for (int end : st) {
                        if (end - i > 0) {
                            System.out.println(i + " " + (end - i));
                        }
                    }
                }
                st.clear();
            }
        }
        
        if (!flag) System.out.println("-1 0");
    }
}

def dfs(i, j, p, t, matches):
    if j == len(p):
        matches.add(i)
        return
    if i == len(t):
        return
        
    if t[i] == p[j]:
        dfs(i + 1, j + 1, p, t, matches)
    elif p[j] == '*':
        dfs(i, j + 1, p, t, matches)
        dfs(i + 1, j, p, t, matches)
        dfs(i + 1, j + 1, p, t, matches)

def solve(p, t):
    flag = False
    for i in range(len(t)):
        if t[i] == p[0] or p[0] == '*':
            matches = set()
            dfs(i, 0, p, t, matches)
            if matches:
                flag = True
                for end in sorted(matches):
                    if end - i > 0:
                        print(i, end - i)
            
    if not flag:
        print("-1 0")

p = input()
t = input()
solve(p, t)

算法及复杂度

• 算法：深度优先搜索（DFS）
• 时间复杂度： - 为模式串长度， 为目标串长度，每个位置有最多3种选择
• 空间复杂度： - 递归栈深度和存储匹配位置的空间