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

题目链接

题目描述

在 Linux Shell 中，通配符 * 代表任意长度（可为 0）的字符串。给定一条模式串 $p$ （仅包含可见字符及通配符 *）和一条目标串 $s$ ，请输出 $s$ 中所有与 $p$ 匹配的子串的起始位置（从 0 开始计）及长度。

若不存在匹配，输出 -1 0。多组匹配按“起始位置升序，长度升序”排序输出。

解题思路

本题解法严格遵循您提供的代码，其核心思路是**遍历所有可能的起始点，并对每个起始点进行一次无记忆化的深度优先搜索（DFS）**来查找所有匹配。

1. 整体框架

主函数通过一个 for 循环，遍历目标串 $s$ 的每一个位置 $i$ （从 $0$ 到 $s.length() - 1$ ），将每个 $i$ 都作为一个潜在匹配的起始点。
对于每一个起始点 $i$ ，调用一个 DFS 函数，来找出从 $i$ 开始，所有能够成功匹配模式串 $p$ 的结束点。

2. 初步剪枝

只有当模式串 $p$ 的第一个字符是 *，或者与目标串的当前字符 s[i] 相同时，才会启动一次新的 DFS。这可以避免大量无效的搜索。

3. 深度优先搜索（DFS）

核心函数 DFS(s_idx, p_idx) 表示尝试从目标串的 s_idx 位置和模式串的 p_idx 位置开始匹配。
成功基线：当 p_idx 到达模式串末尾，意味着匹配成功。此时的 s_idx 被记录为一个合法的结束点。
失败基线：当 s_idx 到达目标串末尾但 p_idx 尚未结束，此路不通，递归返回。
递归逻辑：
- 字符匹配：如果 s[s_idx] == p[p_idx]，则两指针后移，继续匹配 DFS(s_idx + 1, p_idx + 1)。
- 通配符 *：如果 p[p_idx] == '*'，则分三路进行递归探索：
  1. DFS(s_idx, p_idx + 1): * 匹配空串。
  2. DFS(s_idx + 1, p_idx): * 匹配 s[s_idx]，并可能继续匹配后续字符。
  3. DFS(s_idx + 1, p_idx + 1): * 匹配 s[s_idx] 这一个字符。

4. 结果处理

对每个起始点 i，DFS 找到的所有结束点被收集在一个集合中。
遍历该集合，计算并立即输出所有长度大于 0 的匹配 (i, end_pos - i)。
在处理下一个起始点前，清空结果集合。
用一个 flag 标记是否找到过任何匹配，以便在最后输出 -1 0。

注意：此方案为未优化的递归搜索，在面对含有大量 * 和重复字符的复杂用例时，由于没有记忆化，可能因重复计算过多而导致超时。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <set>

using namespace std;

string p_str, s_str;
set<int> end_positions;

// s_idx: 目标串索引, p_idx: 模式串索引
void dfs(int s_idx, int p_idx) {
    if (p_idx == p_str.length()) {
        end_positions.insert(s_idx);
        return; // 关键修正：匹配成功后必须返回，防止后续越界访问
    }
    if (s_idx == s_str.length()) {
        return;
    }
    
    if (p_str[p_idx] == s_str[s_idx]) {
        dfs(s_idx + 1, p_idx + 1);
    } else if (p_str[p_idx] == '*') {
        dfs(s_idx, p_idx + 1);
        dfs(s_idx + 1, p_idx);
        dfs(s_idx + 1, p_idx + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> p_str >> s_str;

    bool found_match = false;
    for (int i = 0; i < s_str.length(); ++i) {
        if (p_str.empty() || p_str[0] == '*' || p_str[0] == s_str[i]) {
            end_positions.clear();
            dfs(i, 0);
            if (!end_positions.empty()) {
                found_match = true;
                for (int end_pos : end_positions) {
                    if (end_pos > i) {
                        cout << i << " " << end_pos - i << "\n";
                    }
                }
            }
        }
    }

    if (!found_match) {
        cout << "-1 0" << endl;
    }

    return 0;
}

import java.util.*;

public class Main {
    static String p_str, s_str;
    static Set<Integer> end_positions;

    static void dfs(int s_idx, int p_idx) {
        if (p_idx == p_str.length()) {
            end_positions.add(s_idx);
            return; // 关键修正：匹配成功后必须返回，防止后续越界访问
        }
        if (s_idx == s_str.length()) {
            return;
        }

        if (p_str.charAt(p_idx) == s_str.charAt(s_idx)) {
            dfs(s_idx + 1, p_idx + 1);
        } else if (p_str.charAt(p_idx) == '*') {
            dfs(s_idx, p_idx + 1);
            dfs(s_idx + 1, p_idx);
            dfs(s_idx + 1, p_idx + 1);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        p_str = sc.next();
        s_str = sc.next();

        boolean found_match = false;
        for (int i = 0; i < s_str.length(); i++) {
            if (p_str.isEmpty() || p_str.charAt(0) == '*' || p_str.charAt(0) == s_str.charAt(i)) {
                end_positions = new TreeSet<>(); // Use TreeSet to keep order
                dfs(i, 0);
                if (!end_positions.isEmpty()) {
                    found_match = true;
                    for (int end_pos : end_positions) {
                        if (end_pos > i) {
                            System.out.println(i + " " + (end_pos - i));
                        }
                    }
                }
            }
        }
        
        if (!found_match) {
            System.out.println("-1 0");
        }
    }
}

import sys

# 提高递归深度限制以防万一
sys.setrecursionlimit(2000)

p_str, s_str = "", ""
end_positions = set()

def dfs(s_idx, p_idx):
    if p_idx == len(p_str):
        end_positions.add(s_idx)
        return # 关键修正：匹配成功后必须返回，防止后续越界访问
    if s_idx == len(s_str):
        return

    if p_str[p_idx] == s_str[s_idx]:
        dfs(s_idx + 1, p_idx + 1)
    elif p_str[p_idx] == '*':
        dfs(s_idx, p_idx + 1)
        dfs(s_idx + 1, p_idx)
        dfs(s_idx + 1, p_idx + 1)

def main():
    global p_str, s_str, end_positions
    p_str = sys.stdin.readline().strip()
    s_str = sys.stdin.readline().strip()
    
    found_match = False
    for i in range(len(s_str)):
        if not p_str or p_str[0] == '*' or p_str[0] == s_str[i]:
            end_positions = set()
            dfs(i, 0)
            if end_positions:
                found_match = True
                # Sort end positions to ensure length-ascending order for a given start
                sorted_ends = sorted(list(end_positions))
                for end_pos in sorted_ends:
                    if end_pos > i:
                        print(f"{i} {end_pos - i}")

    if not found_match:
        print("-1 0")

if __name__ == "__main__":
    main()

算法及复杂度

算法：遍历起始点 + 深度优先搜索 (DFS)
时间复杂度：这是一个未优化的递归解法。在最坏情况下（例如模式串和目标串包含大量 * 和重复字符），DFS 的调用次数会呈指数级增长。其大致的时间复杂度为 $\mathcal{O}(|s| \cdot 3^{|s|+|p|})$ ，无法通过所有性能测试。
空间复杂度：空间复杂度主要由递归调用的栈深度决定。在最坏情况下，栈深度可达 $\mathcal{O}(|s| + |p|)$ 。