刷题笔记合集🔗

增强的strstr

问题描述

C 语言中有一个库函数 char *strstr(const char *haystack, const char *needle)，用于在字符串 haystack 中查找第一次出现字符串 needle 的位置。现在需要实现一个 strstr 的增强函数，支持使用带可选段的字符串进行模糊查询。

可选段使用 "[]" 标识，表示该位置可以是可选段中的任意一个字符。例如，"a[bc]" 可以匹配 "ab" 或 "ac"。

输入格式

输入包含两个字符串，分别是源字符串和目标字符串，以空格分隔。

输出格式

输出一个整数，表示匹配子字符串在源字符串中的起始位置（从 0 开始计数）。如果没有匹配，则输出 -1。

样例输入

abcd b[cd]

样例输出

1

样例解释

目标字符串 "b[cd]" 可以匹配 "bc" 或 "bd"。在源字符串 "abcd" 中，"bc" 子字符串的起始位置是 1。

数据范围

• 源字符串中不包含 '[]'。
• 目标字符串中的 '[]' 成对出现，且不会嵌套。
• 输入的字符串长度在 之间。

题解

这道题的核心是实现一个支持简单模式匹配的字符串查找函数。

虽然可以使用正则表达式来解决，但为了更好地理解问题，我们可以直接实现一个简化版的模式匹配算法。

主要思路如下：

1. 解析目标字符串，将其转换为一个模式数组，其中普通字符直接保存，可选字符用集合表示。
2. 遍历源字符串，对每个位置尝试匹配模式数组。
3. 如果完全匹配，返回当前位置；如果不匹配，继续下一个位置。
4. 如果遍历完源字符串仍未找到匹配，返回 -1。

这种方法的时间复杂度是 ，其中 是源字符串的长度， 是目标字符串的长度。对于给定的数据范围（字符串长度不超过 100），这个复杂度是可以接受的。

参考代码

• Python

def enhanced_strstr(haystack, needle):
    """
    实现增强版的strstr函数
    :param haystack: 源字符串
    :param needle: 目标字符串（可能包含可选段）
    :return: 匹配位置的索引，如果没有匹配则返回-1
    """
    # 解析目标字符串，将其转换为模式数组
    pattern = []
    i = 0
    while i < len(needle):
        if needle[i] == '[':
            # 处理可选段
            options = set()
            i += 1
            while needle[i] != ']':
                options.add(needle[i])
                i += 1
            pattern.append(options)
        else:
            # 处理普通字符
            pattern.append(needle[i])
        i += 1

    # 在源字符串中查找匹配
    for start in range(len(haystack) - len(pattern) + 1):
        match = True
        for i, p in enumerate(pattern):
            if isinstance(p, set):
                if haystack[start + i] not in p:
                    match = False
                    break
            elif haystack[start + i] != p:
                match = False
                break
        if match:
            return start

    return -1

# 读取输入
haystack, needle = input().split()

# 调用函数并输出结果
result = enhanced_strstr(haystack, needle)
print(result)

• C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAX_LEN 101

int enhanced_strstr(const char *haystack, const char *needle) {
    int haystack_len = strlen(haystack);
    int needle_len = strlen(needle);
    char pattern[MAX_LEN][MAX_LEN] = {0};
    int pattern_len = 0;

    // 解析目标字符串，将其转换为模式数组
    int i = 0;
    while (needle[i] != '\0') {
        if (needle[i] == '[') {
            // 处理可选段
            i++;
            int j = 0;
            while (needle[i] != ']') {
                pattern[pattern_len][j++] = needle[i++];
            }
            pattern_len++;
        } else {
            // 处理普通字符
            pattern[pattern_len][0] = needle[i];
            pattern_len++;
        }
        i++;
    }

    // 在源字符串中查找匹配
    for (int start = 0; start <= haystack_len - pattern_len; start++) {
        bool match = true;
        for (int i = 0; i < pattern_len; i++) {
            if (strlen(pattern[i]) > 1) {
                // 可选段
                bool option_match = false;
                for (int j = 0; pattern[i][j] != '\0'; j++) {
                    if (haystack[start + i] == pattern[i][j]) {
                        option_match = true;
                        break;
                    }
                }
                if (!option_match) {
                    match = false;
                    break;
                }
            } else if (haystack[start + i] != pattern[i][0]) {
                // 普通字符
                match = false;