E卷-增强的strstr(100分)
增强的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。
这种方法的时间复杂度是 ，其中
是源字符串的长度，
是目标字符串的长度。对于给定的数据范围（字符串长度不超过 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;
break;
}
}
if (match) {
return start;
}
}
return -1;
}
int main() {
char haystack[MAX_LEN], needle[MAX_LEN];
scanf("%s %s", haystack, needle);
int result = enhanced_strstr(haystack, needle);
printf("%d\n", result);
return 0;
}
- Javascript
function enhancedStrstr(haystack, needle) {
// 解析目标字符串，将其转换为模式数组
const pattern = [];
let i = 0;
while (i < needle.length) {
if (needle[i] === '[') {
// 处理可选段
const options = new Set();
i++;
while (needle[i] !== ']') {
options.add(needle[i]);
i++;
}
pattern.push(options);
} else {
// 处理普通字符
pattern.push(needle[i]);
}
i++;
}
// 在源字符串中查找匹配
for (let start = 0; start <= haystack.length - pattern.length; start++) {
let match = true;
for (let i = 0; i < pattern.length; i++) {
if (pattern[i] instanceof Set) {
if (!pattern[i].has(haystack[start + i])) {
match = false;
break;
}
} else if (haystack[start + i] !== pattern[i]) {
match = false;
break;
}
}
if (match) {
return start;
}
}
return -1;
}
// 读取输入
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('', (input) => {
const [haystack, needle] = input.split(' ');
const result = enhancedStrstr(haystack, needle);
console.log(result);
rl.close();
});
- Java
import java.util.*;
public class Main {
public static int enhancedStrstr(String haystack, String needle) {
// 解析目标字符串，将其转换为模式数组
List<Object> pattern = new ArrayList<>();
int i = 0;
while (i < needle.length()) {
if (needle.charAt(i) == '[') {
// 处理可选段
Set<Character> options = new HashSet<>();
i++;
while (needle.charAt(i) != ']') {
options.add(needle.charAt(i));
i++;
}
pattern.add(options);
} else {
// 处理普通字符
pattern.add(needle.charAt(i));
}
i++;
}
// 在源字符串中查找匹配
for (int start = 0; start <= haystack.length() - pattern.size(); start++) {
boolean match = true;
for (int j = 0; j < pattern.size(); j++) {
Object p = pattern.get(j);
if (p instanceof Set) {
if (!((Set<Character>) p).contains(haystack.charAt(start + j))) {
match = false;
break;
}
} else if ((char) p != haystack.charAt(start + j)) {
match = false;
break;
}
}
if (match) {
return start;
}
}
return -1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String haystack = scanner.next();
String needle = scanner.next();
int result = enhancedStrstr(haystack, needle);
System.out.println(result);
}
}
- Cpp
#include <bits/stdc++.h>
using namespace std;
int enhancedStrstr(const string& haystack, const string& needle) {
// 解析目标字符串，将其转换为模式数组
vector<variant<char, unordered_set<char>>> pattern;
for (size_t i = 0; i < needle.length(); ++i) {
if (needle[i] == '[') {
// 处理可选段
unordered_set<char> options;
++i;
while (needle[i] != ']') {
options.insert(needle[i]);
++i;
}
pattern.push_back(options);
} else {
// 处理普通字符
pattern.push_back(needle[i]);
}
}
// 在源字符串中查找匹配
for (size_t start = 0; start <= haystack.length() - pattern.size(); ++start) {
bool match = true;
for (size_t i = 0; i < pattern.size(); ++i) {
if (holds_alternative<unordered_set<char>>(pattern[i])) {
if (get<unordered_set<char>>(pattern[i]).find(haystack[start + i]) == get<unordered_set<char>>(pattern[i]).end()) {
match = false;
break;
}
} else if (get<char>(pattern[i]) != haystack[start + i]) {
match = false;
break;
}
}
if (match) {
return static_cast<int>(start);
}
}
return -1;
}
int main() {
string haystack, needle;
cin >> haystack >> needle;
int result = enhancedStrstr(haystack, needle);
cout << result << endl;
return 0;
}
OD刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记
投递LINE等公司10个岗位 >
查看18道真题和解析