题面解释:

现要求实现一个类似C语言strstr函数的增强版功能，用于在源字符串中查找带有可选段的目标字符串。可选段由“[]”标识，表示该位置可以匹配括号中任意一个字符，例如“a[bc]”可以匹配“ab”或“ac”。输入为两个字符串，分别是源字符串和带可选段的目标字符串，源字符串长度为1到100且不包含[]符号，目标字符串长度为1到100且[]成对出现且无嵌套。输出为源字符串中第一个匹配目标字符串的位置偏移（从0开始计数），如果没有匹配则返回-1。

题解思路详解：

1. 字符串分层：目标字符串中可能包含带有可选段的字符（用[]括起来），这些可选段表示该位置可以匹配括号内的任意字符。我们将目标字符串按层次分解，每一层要么是单个字符，要么是可选段中的一组字符。

2. 解析目标字符串：遍历目标字符串，当遇到[时，开始记录括号内的字符，当遇到]时，将收集到的字符集合作为一层，存入数组中。对于不在[]中的字符，将其单独作为一层处理。

3. 滑动窗口匹配：滑动窗口的长度等于分解后的目标字符串层数，然后在源字符串中逐个字符滑动，判断每个字符是否能匹配目标字符串的当前层。如果在某个窗口位置内所有字符都能匹配，则输出匹配位置；如果滑动结束后仍未找到匹配，则输出-1。

4. 匹配条件：通过遍历每一层，确保源字符串的字符出现在该层的字符集合中，如果某一层无法匹配，则直接跳出，继续滑动窗口匹配。

代码详解：

1. 输入与初始化：

   • 读取源字符串s和目标字符串tag。
   • 使用vector<set<char>> str存储解析后的目标字符串分层结果。
   • 使用temp临时存储当前可选段的字符集合，mk标志是否处于可选段中。

2. 目标字符串解析：

   • 遍历目标字符串tag，如果遇到[，标记进入可选段，开始收集字符；如果遇到]，将收集的字符集合保存并清空临时集合。对于非可选段字符，直接作为独立的一层保存。

3. 滑动窗口匹配：

   • 使用滑动窗口从源字符串的开头开始滑动，窗口长度为目标字符串分层的层数。
   • 在每个窗口位置逐层检查源字符串的字符是否在目标字符串的对应层的字符集合中。如果全部匹配，输出当前的窗口起始位置；如果某一层不匹配，继续滑动窗口。

4. 结束条件：

   • 如果找到匹配，立即输出匹配位置；如果遍历完整个源字符串仍未找到匹配，则输出-1。

c++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s,tag;
    cin>>s>>tag;
    vector<set<char>>str;
    set<char>temp;
    bool mk=0;
    for(int i=0;i<tag.size();i++)
    {
        char c=tag[i];
        if(c=='[')mk=1;//开始计入temp中
        else if(c==']')
        {
            mk=0;
            str.push_back(temp);
            temp.clear();
        }
        else if(mk)temp.insert(c);
        else str.emplace_back(set<char>{c});
    }
    for(int i=0;i<=s.size()-str.size();i++)
    {
        int j=0;
        while(j<str.size())
        {
            if(str[j].find(s[i+j])==str[j].end())break;//滑动匹配
            j++;
        }
        if(j==str.size())//如果匹配成功
        {
            cout<<i;
            return 0;
        }
    }
    cout<<-1;//没有匹配输出-1
}

python

# 读取输入
s = input()  # 源字符串
tag = input()  # 目标字符串

str_layers = []  # 用于存储每层的字符集合
temp = set()  # 临时集合，用于收集可选段的字符
mk = False  # 标志位，表示是否在可选段中

# 解析目标字符串
for c in tag:
    if c == '[':
        mk = True  # 开始进入可选段
    elif c == ']':
        mk = False  # 结束可选段
        str_layers.append(temp)  # 将收集的可选段字符集合加入str_layers
        temp = set()  # 清空临时集合
    elif mk:
        temp.add(c)  # 在可选段中，收集字符
    else:
        str_layers.append({c})  # 非可选段的字符，单独作为集合加入str_layers

# 滑动窗口匹配
for i in range(len(s) - len(str_layers) + 1):  # 窗口的最大起点为len(s) - len(str_layers)
    j = 0
    while j < len(str_layers):
        # 如果源字符串当前位置的字符不在目标字符串当前层的字符集合中，停止匹配
        if s[i + j] not in str_layers[j]:
            break
        j += 1

    if j == len(str_layers):  # 如果所有层都匹配成功，输出匹配的起始位置
        print(i)
        exit()

# 如果没有匹配，输出-1
print(-1)

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();  // 源字符串
        String tag = sc.next();  // 目标字符串

        List<Set<Character>> strLayers = new ArrayList<>();  // 用于存储每层的字符集合
        Set<Character> temp = new HashSet<>();  // 临时集合，用于收集可选段的字符
        boolean mk = false;  // 标志位，判断是否在可选段中

        // 解析目标字符串
        for (int i = 0; i < tag.length(); i++) {
            char c = tag.charAt(i);
            if (c == '[') {
                mk = true;  // 开始进入可选段
            } else if (c == ']') {
                mk = false;  // 结束可选段
                strLayers.add(new HashSet<>(temp));  // 将可选段的字符集合存入strLayers
                temp.clear();  // 清空临时集合
            } else if (mk) {
                temp.add(c);  // 在可选段中收集字符
            } else {
                // 非可选段的字符直接作为一个集合存入strLayers
                strLayers.add(new HashSet<>(Collections.singleton(c)));
            }
        }

        // 滑动窗口匹配
        for (int i = 0; i <= s.length() - strLayers.size(); i++) {
            int j = 0;
            while (j < strLayers.size()) {
                // 如果当前字符不在该层的字符集合中，停止匹配
                if (!strLayers.get(j).contains(s.charAt(i + j))) {
                    break;
                }
                j++;
            }

            // 如果所有层都匹配成功，输出匹配的起始位置并结束
            if (j == strLayers.size()) {
                System.out.println(i);
                return;
            }
        }

        // 如果没有匹配，输出-1
        System.out.println(-1);
    }
}

题目描述

$C$ 语言有一个库函数： char *strstr(const char *haystack, const char *needle) ，实现在字符串 $haystack$ 中查找第一次出现字符串 $needle$ 的位置，如果未找到则返回 $null$。

现要求实现一个$strstr$的增强函数，可以使用带可选段的字符串来模糊查询，与$strstr$一样返回首次查找到的字符串位置。

可选段使用“[]”标识，表示该位置是可选段中任意一个字符即可满足匹配条件。比如“$a[bc]$”表示可以匹配“$ab$”或“$ac$”。

注意目标字符串中可选段可能出现多次。

输入描述

与$strstr$函数一样，输入参数是两个字符串指针，分别是源字符串和目标字符串。

输出描述

与$strstr$函数不同，返回的是源字符串中，匹配子字符串相对于源字符串地址的偏移（从$0$开始算），如果没有匹配返回$-1$。

补充说明：源字符串中必定不包含‘[]’；目标字符串中‘[]’必定成对出现，且不会出现嵌套。

输入的字符串长度在$[1,100]$之间。

样例1

输入

abcd
b[cd]

输出

1

说明

相当于是在源字符串中查找bc或者bd，bc子字符串相对于abcd的偏移是1