2025B-增强的strstr-100分

问题描述

小基是一名程序员，他正在开发一个文本处理工具。他需要实现一个增强版的字符串查找功能，类似于C语言中的strstr函数，但具有更多的功能。

具体来说，他需要实现以下功能：

1. 在主字符串中查找模式字符串的所有出现位置（而不仅仅是第一次出现的位置）。
2. 支持通配符匹配：模式字符串中的*可以匹配任意长度（包括0）的任意字符序列。

例如，在主字符串"abcabcabc"中查找模式字符串"abc"，应该返回出现位置[0, 3, 6]。如果查找模式字符串"a*c"，应该返回出现位置[0, 3, 6]，因为*可以匹配字符'b'。

请你帮助小基实现这个增强版的字符串查找功能。

输入格式

第一行包含一个字符串 ，表示主字符串。

第二行包含一个字符串 ，表示模式字符串。

输出格式

如果模式字符串在主字符串中有匹配，则输出所有匹配的起始位置（从0开始计数），位置之间用空格分隔。

如果没有匹配，则输出 "-1"。

样例输入1

abcabcabc
abc

样例输出1

0 3 6

样例输入2

abcabcabc
a*c

样例输出2

0 3 6

样例输入3

abcdefg
xyz

样例输出3

-1

样例输入4

aaaaa
a*a

样例输出4

0 1 2 3

样例输入5

abcdefabcdef
*def

样例输出5

3 9

样例解释

数据范围

• 
• 和 只包含小写字母和通配符 *
• 中最多包含 个通配符 *

题解

这道题目要求我们实现一个增强版的字符串查找功能，支持通配符匹配。关键点在于如何处理模式字符串中的通配符*。

解题思路如下：

1. 如果模式字符串中不包含通配符*，那么这就是一个简单的字符串匹配问题，我们可以使用暴力匹配、KMP算法或其他字符串匹配算法来解决。

2. 如果模式字符串中包含通配符*，我们需要特殊处理。一种方法是将模式字符串按照*分割成多个子串，然后在主字符串中依次查找这些子串。

   例如，对于模式字符串"a*c"，我们可以将其分割成["a", "c"]，然后在主字符串中查找这两个子串，要求它们按顺序出现，中间可以有任意字符。

3. 具体实现时，我们可以使用动态规划或回溯法来处理通配符匹配。在这里，我们采用一种贪心的方法：从左到右扫描主字符串，尝试匹配模式字符串的每个部分。

时间复杂度分析：

• 在最坏情况下，我们需要检查主字符串的每个位置是否可以开始一个匹配，这需要O(|s|)的时间。
• 对于每个可能的起始位置，我们需要尝试匹配整个模式字符串，这需要O(|s| + |p|)的时间。
• 因此，总时间复杂度为O(|s| * (|s| + |p|))。

空间复杂度分析：

• 我们需要存储模式字符串分割后的子串，这需要O(|p|)的空间。
• 我们还需要存储所有匹配的位置，这需要O(|s|)的空间（在最坏情况下，每个位置都是一个匹配的起始位置）。
• 因此，总空间复杂度为O(|s| + |p|)。

对于给定的数据范围（|s|, |p| ≤ 10^5），这个算法的效率可能不够高。但考虑到模式字符串中最多只有10个通配符，我们可以优化算法，使其在实际情况下表现良好。

参考代码

def solve():
    # 读取主字符串和模式字符串
    s = input().strip()
    p = input().strip()
    
    # 查找所有匹配位置
    positions = find_all_matches(s, p)
    
    # 输出结果
    if positions:
        print(" ".join(map(str, positions)))
    else:
        print("-1")

def find_all_matches(s, p):
    """
    在主字符串s中查找模式字符串p的所有匹配位置
    
    参数:
        s: 主字符串
        p: 模式字符串，可能包含通配符*
    
    返回:
        匹配的起始位置列表
    """
    # 如果模式字符串不包含通配符，使用简单的字符串匹配
    if '*' not in p:
        return find_substring(s, p)
    
    # 将模式字符串按*分割
    parts = p.split('*')
    
    # 存储所有匹配的起始位置
    result = []
    
    # 遍历主字符串的每个位置，检查是否可以开始一个匹配
    for i in range(len(s)):
        if is_match(s, i, parts):
            result.append(i)
    
    return result

def find_substring(s, sub):
    """
    在字符串s中查找子串sub的所有出现位置
    
    参数:
        s: 主字符串
        sub: 子字符串
    
    返回:
        子串在主字符串中的所有起始位置
    """
    result = []
    sub_len = len(sub)
    
    # 遍历主字符串的每个可能的起始位置
    for i in range(len(s) - sub_len + 1):
        if s[i:i+sub_len] == sub:
            result.append(i)
    
    return result

def is_match(s, start, parts):
    """
    检查从start位置开始，s是否匹配由*分割的模式部分
    
    参数:
        s: 主字符串
        start: 起始位置
        parts: 模式字符串按*分割的部分
    
    返回:
        是否匹配
    """
    curr_pos = start
    
    # 检查第一部分是否匹配
    if parts[0] and not s[curr_pos:].startswith(parts[0]):
        return False
    
    curr_pos += len(parts[0])
    
    # 依次检查剩余部分
    for i in range(1, len(parts)):
        part = parts[i]
        
        # 如果已经到达字符串末尾但还有部分需要匹配
        if curr_pos >= len(s) and part:
            return False
        
        # 查找当前部分在剩余字符串中的位置
        if part:
            pos = s.find(part, curr_pos)
            if pos == -1:
                return False
            curr_pos = pos + len(part)
        
    return True

if __name__ == "__main__":
    solve()

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

/**
 * 在字符串s中查找子串sub的所有出现位置
 * 
 * @param s 主字符串
 * @param sub 子字符串
 * @return 子串在主字符串中的所有起始位置
 */
vector<int> findSubstring(const string& s, const string& sub) {
    vector<int> result;
    int subLen = su