【2024年华为OD机试】(B卷,100分)- 增强的strstr （Java JS PythonC/C++）

一、问题描述

题目描述

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

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

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

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

输入描述

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

输出描述

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

补充说明

1. 源字符串中必定不包含 []。
2. 目标字符串中 [] 必定成对出现，且不会出现嵌套。
3. 输入的字符串长度在 [1, 100] 之间。

用例

用例 1

输入

abcd
b[cd]

输出

1

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

---

题目解析

问题分析

我们需要实现一个增强版的 strstr 函数，支持目标字符串中包含可选段 []。可选段表示该位置可以是任意一个字符，只要满足可选段中的任意一个字符即可匹配。

例如：

• 目标字符串 a[bc] 可以匹配 ab 或 ac。
• 目标字符串 [ab]c 可以匹配 ac 或 bc。

解题思路

方法 1：正则表达式（套皮解法）

1. 正则表达式匹配：

   • 目标字符串中的 [] 可以直接对应正则表达式中的字符组 []。
   • 例如，目标字符串 a[bc] 可以转换为正则表达式 a[bc]，匹配 ab 或 ac。

2. 实现步骤：

   • 将目标字符串转换为正则表达式。
   • 使用正则表达式库在源字符串中查找匹配的子字符串。
   • 返回匹配子字符串的偏移量。

3. 优缺点：

   • 优点：实现简单，代码量少。
   • 缺点：如果目标字符串中包含其他正则元字符（如 .、* 等），可能会影响匹配结果。

方法 2：分层匹配（稳健解法）

1. 目标字符串分层：

   • 将目标字符串按 [] 分割成多个层级。
   • 例如，目标字符串 b[cd] 可以分为两层：
     • 第一层：b。
     • 第二层：c 或 d。

2. 滑窗匹配：

   • 使用滑动窗口在源字符串中查找匹配的子字符串。
   • 滑动窗口的长度为目标字符串的层数。
   • 对于每个窗口，逐层检查是否匹配目标字符串的每一层。

3. 实现步骤：

   • 解析目标字符串，提取每一层的可选字符。
   • 在源字符串中使用滑动窗口逐字符匹配。
   • 如果匹配成功，返回当前窗口的起始偏移量。

4. 优缺点：

   • 优点：稳健，不受正则元字符影响。
   • 缺点：实现稍微复杂，需要手动解析目标字符串。

---

示例解析

示例 1

输入

abcd
b[cd]

解析

1. 目标字符串 b[cd] 分为两层：
   • 第一层：b。
   • 第二层：c 或 d。
2. 在源字符串 abcd 中滑动窗口匹配：
   • 窗口 ab：第一层 b 匹配，第二层 c 不匹配。
   • 窗口 bc：第一层 b 匹配，第二层 c 匹配。
   • 匹配成功，返回偏移量 1。

---

总结

• 正则表达式解法：

  • 适合目标字符串中不包含其他正则元字符的情况。
  • 实现简单，但可能存在匹配错误的风险。

• 分层匹配解法：

  • 稳健，适用于所有情况。
  • 需要手动解析目标字符串，实现稍复杂。

根据题目要求和实际场景，可以选择合适的解法。

二、JavaScript算法源码

滑窗解法

以下是 JavaScript 代码的详细注释和讲解，帮助理解每一部分的功能和实现逻辑：

---

代码结构

1. 输入获取：

   • 使用 readline 模块从控制台读取源字符串和目标字符串。

2. 目标字符串解析：

   • 将目标字符串解析为多层结构，每一层表示可选字符的集合。

3. 滑动窗口匹配：

   • 使用滑动窗口在源字符串中查找匹配的子字符串。

4. 输出结果：

   • 返回匹配子字符串的偏移量，如果没有匹配则返回 -1。

---

代码逐行解析

1. 输入获取

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;void (async function () {const src = await readline(); // 读取源字符串const tar = await readline(); // 读取目标字符串

• 功能：
  • 使用 readline 模块从控制台读取源字符串和目标字符串。
• 关键点：
  • src 是源字符串。
  • tar 是目标字符串。

---

2. 目标字符串解析

  // 将tar字符串转化为levels多层结构，转化逻辑为：tar字符串中，每个[]包含的所有字符作为一层，未被[]包含的单个字符作为一层const levels = [];// level用于记录[]中的字符let level = new Set();let isOpen = false;for (let c of tar) {switch (c) {case "[":isOpen = true;break;case "]":isOpen = false;levels.push(level);level = new Set();break;default:if (isOpen) {level.add(c);} else {levels.push(new Set([c]));}}}

• 功能：
  • 将目标字符串解析为多层结构，每一层表示可选字符的集合。
• 关键点：
  • levels 数组：
    • 存储每一层的可选字符集合。
  • level 集合：
    • 用于记录 [] 中的字符。
  • isOpen 标志：
    • 表示当前是否处于 [] 中。
  • 解析逻辑：
    • 遇到 [，开始记录可选字符。
    • 遇到 ]，将当前 level 加入 levels，并重置 level。
    • 遇到普通字符，如果不在 [] 中，则直接作为一层加入 levels。

---

3. 滑动窗口匹配

  console.log(indexOf());function indexOf() {// 滑动匹配levels.length长度的子串for (let i = 0; i <= src.length - levels.length; i++) {let isFind = true;for (let j = 0; j < levels.length; j++) {if (!levels[j].has(src[i + j])) {isFind = false;break;}}if (isFind) {return i;}}return -1;}
})();

• 功能：
  • 使用滑动窗口在源字符串中查找匹配的子字符串。
• 关键点：
  • 滑动窗口：
    • 窗口长度为 levels.length。
    • 在源字符串中逐字符滑动窗口。
  • 匹配逻辑：
    • 对于每个窗口，逐层检查是否匹配目标字符串的每一层。
    • 如果所有层都匹配，则返回当前窗口的起始偏移量。
  • 返回值：
    • 如果找到匹配，返回偏移量。
    • 如果未找到匹配，返回 -1。

---

示例运行

输入

abcd
b[cd]

执行过程

1. 读取输入：

   • 源字符串 src = "abcd"。
   • 目标字符串 tar = "b[cd]"。

2. 目标字符串解析：

   • 解析结果为 levels = [Set{'b'}, Set{'c', 'd'}]。

3. 滑动窗口匹配：

   • 窗口长度 levels.length = 2。
   • 滑动窗口匹配：
     • 窗口 ab：第一层 b 匹配，第二层 c 不匹配。
     • 窗口 bc：第一层 b 匹配，第二层 c 匹配。
     • 匹配成功，返回偏移量 1。

输出

1

---

代码总结

• 优点：

  • 使用滑动窗口和分层匹配，逻辑清晰，易于理解。
  • 支持目标字符串中的可选段 []。

• 适用场景：

  • 适用于目标字符串中包含可选段的情况。

---

代码注释完整版

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;void (async function () {const src = await readline(); // 读取源字符串const tar = await readline(); // 读取目标字符串// 将tar字符串转化为levels多层结构，转化逻辑为：tar字符串中，每个[]包含的所有字符作为一层，未被[]包含的单个字符作为一层const levels = [];// level用于记录[]中的字符let level = new Set();let isOpen = false;for (let c of tar) {switch (c) {case "[":isOpen = true;break;case "]":isOpen = false;levels.push(level);level = new Set();break;default:if (isOpen) {level.add(c);} else {levels.push(new Set([c]));}}}console.log(indexOf());function indexOf() {// 滑动匹配levels.length长度的子串for (let i = 0; i <= src.length - levels.length; i++) {let isFind = true;for (let j = 0; j < levels.length; j++) {if (!levels[j].has(src[i + j])) {isFind = false;break;}}if (isFind) {return i;}}return -1;}
})();

通过以上注释和讲解，可以清晰地理解 JavaScript 代码的每一部分功能和实现逻辑。

正则解法

以下是 JavaScript 代码的详细注释和讲解，帮助理解每一部分的功能和实现逻辑：

---

代码结构

1. 输入获取：

   • 使用 readline 模块从控制台读取源字符串和目标字符串。

2. 正则表达式匹配：

   • 使用正则表达式在源字符串中查找匹配的子字符串。

3. 输出结果：

   • 返回匹配子字符串的偏移量，如果没有匹配则返回 -1。

---

代码逐行解析

1. 输入获取

const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});const lines = [];
rl.on("line", (line) => {lines.push(line);if (lines.length == 2) {console.log(getResult(lines[0], lines[1]));lines.length = 0;}
});

• 功能：
  • 使用 readline 模块从控制台读取源字符串和目标字符串。
• 关键点：
  • lines 数组用于存储输入的行数据。
  • 当输入行数为 2 时，调用 getResult 函数计算结果并输出。

---

2. 正则表达式匹配

function getResult(src, tar) {const res = new RegExp(tar).exec(src);if (res && res.length > 0) {return src.indexOf(res[0]);} else {return -1;}
}

• 功能：
  • 使用正则表达式在源字符串中查找匹配的子字符串。
• 关键点：
  • new RegExp(tar)：
    • 将目标字符串 tar 转换为正则表达式。
  • exec(src)：
    • 在源字符串 src 中执行正则表达式匹配。
    • 返回匹配结果数组 res，如果没有匹配则返回 null。
  • 匹配结果处理：
    • 如果匹配成功，返回匹配子字符串的偏移量。
    • 如果匹配失败，返回 -1。

---

示例运行

输入

abcd
b[cd]

执行过程

1. 读取输入：

   • 源字符串 src = "abcd"。
   • 目标字符串 tar = "b[cd]"。

2. 正则表达式匹配：

   • 将 tar 转换为正则表达式 b[cd]。
   • 在 src 中查找匹配的子字符串。
   • 匹配结果为 bc，偏移量为 1。

3. 输出结果：

   • 返回偏移量 1。

输出

1

---

代码总结

• 优点：

  • 实现简单，代码量少。
  • 直接利用正则表达式的功能，支持目标字符串中的可选段 []。

• 缺点：

  • 如果目标字符串中包含其他正则元字符（如 .、* 等），可能会影响匹配结果。

• 适用场景：

  • 适用于目标字符串中不包含其他正则元字符的情况。

---

代码注释完整版

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});const lines = [];
rl.on("line", (line) => {lines.push(line);if (lines.length == 2) {console.log(getResult(lines[0], lines[1]));lines.length = 0;}
});function getResult(src, tar) {const res = new RegExp(tar).exec(src); // 使用正则表达式在源字符串中查找匹配的子字符串if (res && res.length > 0) {return src.indexOf(res[0]); // 返回匹配子字符串的偏移量} else {return -1; // 如果没有匹配，返回 -1}
}

通过以上注释和讲解，可以清晰地理解 JavaScript 代码的每一部分功能和实现逻辑。

三、Java算法源码

滑窗解法

以下是 Java 代码的详细注释和讲解，帮助理解每一部分的功能和实现逻辑：

---

代码结构

1. 输入获取：

   • 使用 Scanner 从控制台读取源字符串和目标字符串。

2. 目标字符串解析：

   • 将目标字符串解析为多层结构，每一层表示可选字符的集合。

3. 滑动窗口匹配：

   • 使用滑动窗口在源字符串中查找匹配的子字符串。

4. 输出结果：

   • 返回匹配子字符串的偏移量，如果没有匹配则返回 -1。

---

代码逐行解析

1. 输入获取

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String src = sc.nextLine(); // 读取源字符串String tar = sc.nextLine(); // 读取目标字符串System.out.println(getResult(src, tar)); // 调用 getResult 函数并输出结果}

• 功能：
  • 使用 Scanner 从控制台读取源字符串和目标字符串。
• 关键点：
  • src 是源字符串。
  • tar 是目标字符串。

---

2. 目标字符串解析

  public static int getResult(String src, String tar) {// 将tar字符串转化为levels多层结构，转化逻辑为：tar字符串中，每个[]包含的所有字符作为一层，未被[]包含的单个字符作为一层ArrayList<HashSet<Character>> levels = new ArrayList<>();// level用于记录[]中的字符HashSet<Character> level = new HashSet<>();boolean isOpen = false;for (int i = 0; i < tar.length(); i++) {char c = tar.charAt(i);switch (c) {case '[':isOpen = true;break;case ']':isOpen = false;levels.add(level);level = new HashSet<>();break;default:if (isOpen) {level.add(c);} else {HashSet<Character> tmp = new HashSet<>();tmp.add(c);levels.add(tmp);}}}return indexOf(src, levels);}

• 功能：
  • 将目标字符串解析为多层结构，每一层表示可选字符的集合。
• 关键点：
  • levels 列表：
    • 存储每一层的可选字符集合。
  • level 集合：
    • 用于记录 [] 中的字符。
  • isOpen 标志：
    • 表示当前是否处于 [] 中。
  • 解析逻辑：
    • 遇到 [，开始记录可选字符。
    • 遇到 ]，将当前 level 加入 levels，并重置 level。
    • 遇到普通字符，如果不在 [] 中，则直接作为一层加入 levels。

---

3. 滑动窗口匹配

  public static int indexOf(String src, ArrayList<HashSet<Character>> levels) {// 滑动匹配levels.length长度的子串for (int i = 0; i <= src.length() - levels.size(); i++) {boolean isFind = true;for (int j = 0; j < levels.size(); j++) {if (!levels.get(j).contains(src.charAt(i + j))) {isFind = false;break;}}if (isFind) return i;}return -1;}
}

• 功能：
  • 使用滑动窗口在源字符串中查找匹配的子字符串。
• 关键点：
  • 滑动窗口：
    • 窗口长度为 levels.size()。
    • 在源字符串中逐字符滑动窗口。
  • 匹配逻辑：
    • 对于每个窗口，逐层检查是否匹配目标字符串的每一层。
    • 如果所有层都匹配，则返回当前窗口的起始偏移量。
  • 返回值：
    • 如果找到匹配，返回偏移量。
    • 如果未找到匹配，返回 -1。

---

示例运行

输入

abcd
b[cd]

执行过程

1. 读取输入：

   • 源字符串 src = "abcd"。
   • 目标字符串 tar = "b[cd]"。

2. 目标字符串解析：

   • 解析结果为 levels = [Set{'b'}, Set{'c', 'd'}]。

3. 滑动窗口匹配：

   • 窗口长度 levels.size() = 2。
   • 滑动窗口匹配：
     • 窗口 ab：第一层 b 匹配，第二层 c 不匹配。
     • 窗口 bc：第一层 b 匹配，第二层 c 匹配。
     • 匹配成功，返回偏移量 1。

输出

1

---

代码总结

• 优点：

  • 使用滑动窗口和分层匹配，逻辑清晰，易于理解。
  • 支持目标字符串中的可选段 []。

• 适用场景：

  • 适用于目标字符串中包含可选段的情况。

---

代码注释完整版

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String src = sc.nextLine(); // 读取源字符串String tar = sc.nextLine(); // 读取目标字符串System.out.println(getResult(src, tar)); // 调用 getResult 函数并输出结果}public static int getResult(String src, String tar) {// 将tar字符串转化为levels多层结构，转化逻辑为：tar字符串中，每个[]包含的所有字符作为一层，未被[]包含的单个字符作为一层ArrayList<HashSet<Character>> levels = new ArrayList<>();// level用于记录[]中的字符HashSet<Character> level = new HashSet<>();boolean isOpen = false;for (int i = 0; i < tar.length(); i++) {char c = tar.charAt(i);switch (c) {case '[':isOpen = true;break;case ']':isOpen = false;levels.add(level);level = new HashSet<>();break;default:if (isOpen) {level.add(c);} else {HashSet<Character> tmp = new HashSet<>();tmp.add(c);levels.add(tmp);}}}return indexOf(src, levels);}public static int indexOf(String src, ArrayList<HashSet<Character>> levels) {// 滑动匹配levels.length长度的子串for (int i = 0; i <= src.length() - levels.size(); i++) {boolean isFind = true;for (int j = 0; j < levels.size(); j++) {if (!levels.get(j).contains(src.charAt(i + j))) {isFind = false;break;}}if (isFind) return i;}return -1;}
}

通过以上注释和讲解，可以清晰地理解 Java 代码的每一部分功能和实现逻辑。

正则解法

：

// 导入所需的Java工具类
import java.util.Scanner; // 用于从控制台读取用户输入
import java.util.regex.Matcher; // 用于匹配正则表达式
import java.util.regex.Pattern; // 用于编译正则表达式// 定义主类Main
public class Main {// 主方法，程序的入口public static void main(String[] args) {// 创建一个Scanner对象，用于从控制台读取用户输入Scanner sc = new Scanner(System.in);// 读取用户输入的第一行，作为源字符串（src）String src = sc.nextLine();// 读取用户输入的第二行，作为目标字符串（tar）String tar = sc.nextLine();// 调用getResult方法，传入src和tar，并输出结果System.out.println(getResult(src, tar));}// 定义getResult方法，用于查找目标字符串在源字符串中的起始位置public static int getResult(String src, String tar) {// 使用Pattern.compile(tar)将目标字符串编译为正则表达式模式// 然后使用matcher(src)创建一个Matcher对象，用于在源字符串中查找匹配Matcher matcher = Pattern.compile(tar).matcher(src);// 使用matcher.find()方法尝试在源字符串中查找与目标字符串匹配的子串if (matcher.find()) {// 如果找到匹配的子串，使用matcher.group()获取匹配的子串// 然后使用src.indexOf(matcher.group())获取该子串在源字符串中的起始位置return src.indexOf(matcher.group());} else {// 如果没有找到匹配的子串，返回-1表示未找到return -1;}}
}

代码详细讲解：

1. 导入工具类：

   • java.util.Scanner：用于从控制台读取用户输入。
   • java.util.regex.Matcher：用于匹配正则表达式。
   • java.util.regex.Pattern：用于编译正则表达式。

2. 主类 Main：

   • 这是程序的入口类，包含 main 方法和 getResult 方法。

3. main 方法：

   • 创建一个 Scanner 对象 sc，用于从控制台读取用户输入。
   • 使用 sc.nextLine() 读取用户输入的两行字符串，分别赋值给 src（源字符串）和 tar（目标字符串）。
   • 调用 getResult(src, tar) 方法，传入 src 和 tar，并输出结果。

4. getResult 方法：

   • 该方法用于查找目标字符串在源字符串中的起始位置。
   • 使用 Pattern.compile(tar) 将目标字符串编译为正则表达式模式。
   • 使用 matcher(src) 创建一个 Matcher 对象，用于在源字符串中查找匹配。
   • 使用 matcher.find() 方法尝试在源字符串中查找与目标字符串匹配的子串：
     • 如果找到匹配的子串，使用 matcher.group() 获取匹配的子串，然后使用 src.indexOf(matcher.group()) 获取该子串在源字符串中的起始位置，并返回该位置。
     • 如果没有找到匹配的子串，返回 -1 表示未找到。

示例运行：

输入：

Hello, world!
world

输出：

7

解释：

• 源字符串 src 是 "Hello, world!"。
• 目标字符串 tar 是 "world"。
• 在 src 中查找 tar，发现 "world" 从索引 7 开始，因此返回 7。

输入：

Hello, world!
java

输出：

-1

解释：

• 源字符串 src 是 "Hello, world!"。
• 目标字符串 tar 是 "java"。
• 在 src 中未找到 "java"，因此返回 -1。

总结：

• 该代码的功能是查找目标字符串在源字符串中的起始位置。
• 使用正则表达式进行匹配，如果找到匹配的子串，则返回其起始位置；否则返回 -1。
• 代码逻辑清晰，未做任何优化，适合初学者理解正则表达式和字符串匹配的基本用法。

四、Python算法源码

滑窗解法

以下是您提供的 Python 代码的详细注释和讲解，并转换为 C++ 和 C 语言的实现。

---

Python 代码详细注释

# 输入获取
src = input()  # 读取源字符串
tar = input()  # 读取目标字符串# 定义 indexOf 函数，用于在源字符串中查找匹配的子串
def indexOf(levels):# 滑动匹配 levels 长度的子串for i in range(len(src) - len(levels) + 1):isFind = True  # 标记是否找到匹配# 检查当前子串是否匹配 levels 的每一层for j in range(len(levels)):if src[i + j] not in levels[j]:  # 如果字符不在当前层中isFind = Falsebreakif isFind:  # 如果找到匹配，返回起始位置return ireturn -1  # 如果未找到匹配，返回 -1# 定义核心函数 getResult
def getResult():# 将 tar 字符串转化为 levels 多层结构# 转化逻辑为：tar 字符串中，每个 [] 包含的所有字符作为一层，未被 [] 包含的单个字符作为一层levels = []  # 用于存储每一层的字符集合level = set()  # 用于记录 [] 中的字符isOpen = False  # 标记是否正在解析 [] 中的内容for c in tar:if c == '[':isOpen = True  # 开始解析 [] 中的内容elif c == ']':isOpen = False  # 结束解析 [] 中的内容levels.append(level)  # 将当前层添加到 levelslevel = set()  # 重置当前层else:if isOpen:level.add(c)  # 将字符添加到当前层else:levels.append({c})  # 将单个字符作为一层# 调用 indexOf 函数查找匹配return indexOf(levels)# 算法调用
print(getResult())

---

C++ 实现

#include <iostream>
#include <vector>
#include <set>
#include <string>using namespace std;// 定义 indexOf 函数，用于在源字符串中查找匹配的子串
int indexOf(const string& src, const vector<set<char>>& levels) {// 滑动匹配 levels 长度的子串for (size_t i = 0; i <= src.length() - levels.size(); ++i) {bool isFind = true;  // 标记是否找到匹配// 检查当前子串是否匹配 levels 的每一层for (size_t j = 0; j < levels.size(); ++j) {if (levels[j].find(src[i + j]) == levels[j].end()) {  // 如果字符不在当前层中isFind = false;break;}}if (isFind) {  // 如果找到匹配，返回起始位置return i;}}return -1;  // 如果未找到匹配，返回 -1
}// 定义核心函数 getResult
int getResult(const string& src, const string& tar) {vector<set<char>> levels;  // 用于存储每一层的字符集合set<char> level;           // 用于记录 [] 中的字符bool isOpen = false;       // 标记是否正在解析 [] 中的内容for (char c : tar) {if (c == '[') {isOpen = true;  // 开始解析 [] 中的内容} else if (c == ']') {isOpen = false;  // 结束解析 [] 中的内容levels.push_back(level);  // 将当前层添加到 levelslevel.clear();            // 重置当前层} else {if (isOpen) {level.insert(c);  // 将字符添加到当前层} else {levels.push_back({c});  // 将单个字符作为一层}}}// 调用 indexOf 函数查找匹配return indexOf(src, levels);
}int main() {// 输入获取string src, tar;getline(cin, src);  // 读取源字符串getline(cin, tar);  // 读取目标字符串// 调用核心函数并输出结果cout << getResult(src, tar) << endl;return 0;
}

---

C 语言实现

C 语言没有内置的集合和动态数组，因此需要使用数组和手动管理内存。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_LEVELS 1000  // 最大层数
#define MAX_CHARS 128    // 每层最大字符数// 定义 indexOf 函数，用于在源字符串中查找匹配的子串
int indexOf(const char* src, char levels[MAX_LEVELS][MAX_CHARS], int levelsCount) {int srcLen = strlen(src);int levelsLen = levelsCount;// 滑动匹配 levels 长度的子串for (int i = 0; i <= srcLen - levelsLen; ++i) {int isFind = 1;  // 标记是否找到匹配// 检查当前子串是否匹配 levels 的每一层for (int j = 0; j < levelsLen; ++j) {char c = src[i + j];int isInLevel = 0;// 检查字符是否在当前层中for (int k = 0; levels[j][k] != '\0'; ++k) {if (levels[j][k] == c) {isInLevel = 1;break;}}if (!isInLevel) {  // 如果字符不在当前层中isFind = 0;break;}}if (isFind) {  // 如果找到匹配，返回起始位置return i;}}return -1;  // 如果未找到匹配，返回 -1
}// 定义核心函数 getResult
int getResult(const char* src, const char* tar) {char levels[MAX_LEVELS][MAX_CHARS];  // 用于存储每一层的字符集合int levelsCount = 0;                 // 当前层数char level[MAX_CHARS];               // 用于记录 [] 中的字符int levelIndex = 0;                  // 当前层的字符索引int isOpen = 0;                      // 标记是否正在解析 [] 中的内容for (int i = 0; tar[i] != '\0'; ++i) {char c = tar[i];if (c == '[') {isOpen = 1;  // 开始解析 [] 中的内容levelIndex = 0;} else if (c == ']') {isOpen = 0;  // 结束解析 [] 中的内容level[levelIndex] = '\0';  // 结束当前层strcpy(levels[levelsCount++], level);  // 将当前层添加到 levels} else {if (isOpen) {level[levelIndex++] = c;  // 将字符添加到当前层} else {level[0] = c;  // 将单个字符作为一层level[1] = '\0';strcpy(levels[levelsCount++], level);}}}// 调用 indexOf 函数查找匹配return indexOf(src, levels, levelsCount);
}int main() {// 输入获取char src[1000], tar[1000];fgets(src, sizeof(src), stdin);  // 读取源字符串fgets(tar, sizeof(tar), stdin);  // 读取目标字符串// 去掉输入字符串末尾的换行符src[strcspn(src, "\n")] = '\0';tar[strcspn(tar, "\n")] = '\0';// 调用核心函数并输出结果printf("%d\n", getResult(src, tar));return 0;
}

---

总结：

• Python 实现：使用集合和列表，代码简洁，适合快速开发。
• C++ 实现：使用 std::set 和 std::vector，代码清晰，功能强大。
• C 语言实现：使用数组和手动管理内存，适合嵌入式或性能敏感场景。

三种实现的功能一致，适合不同场景下的开发需求。

正则解法

# 导入正则表达式模块 re，用于处理字符串匹配
import re# 从控制台读取用户输入的第一行，作为源字符串（src）
src = input()
# 从控制台读取用户输入的第二行，作为目标字符串（tar）
tar = input()# 定义核心函数 getResult，用于查找目标字符串在源字符串中的起始位置
def getResult():# 使用 re.search(tar, src) 在源字符串 src 中查找目标字符串 tar# re.search 会返回一个匹配对象（Match 对象）或 None（如果未找到匹配）res = re.search(tar, src)# 判断是否找到匹配if res is None:# 如果未找到匹配，返回 -1return -1else:# 如果找到匹配，返回匹配的起始位置（res.start()）return res.start()# 调用 getResult 函数，并输出结果
print(getResult())

代码详细讲解：

1. 导入模块：

   • import re：导入 Python 的正则表达式模块 re，用于处理字符串匹配。

2. 输入获取：

   • 使用 input() 函数从控制台读取用户输入的两行字符串，分别赋值给 src（源字符串）和 tar（目标字符串）。

3. 核心函数 getResult：

   • 该函数用于查找目标字符串在源字符串中的起始位置。
   • 使用 re.search(tar, src) 在源字符串 src 中查找目标字符串 tar：
     • re.search 会返回一个匹配对象（Match 对象）或 None（如果未找到匹配）。
   • 判断匹配结果：
     • 如果 res 是 None，表示未找到匹配，返回 -1。
     • 如果 res 不是 None，表示找到匹配，使用 res.start() 获取匹配的起始位置，并返回该位置。

4. 算法调用：

   • 调用 getResult() 函数，并输出结果。

示例运行：

输入：

Hello, world!
world

输出：

7

解释：

• 源字符串 src 是 "Hello, world!"。
• 目标字符串 tar 是 "world"。
• 在 src 中查找 tar，发现 "world" 从索引 7 开始，因此返回 7。

输入：

Hello, world!
java

输出：

-1

解释：

• 源字符串 src 是 "Hello, world!"。
• 目标字符串 tar 是 "java"。
• 在 src 中未找到 "java"，因此返回 -1。

总结：

• 该代码的功能是查找目标字符串在源字符串中的起始位置。
• 使用 re.search 进行正则表达式匹配，如果找到匹配的子串，则返回其起始位置；否则返回 -1。
• 代码逻辑清晰，未做任何优化，适合初学者理解正则表达式和字符串匹配的基本用法。

对比 Java 和 Python 的实现：

• Java 的实现使用了 Pattern 和 Matcher 类，而 Python 的实现使用了 re 模块。
• Python 的代码更加简洁，适合快速开发和原型设计。
• Java 的代码更加面向对象，适合大型项目和严格的类型检查场景。

五、C/C++算法源码：

滑窗解法

---

C++ 实现

#include <iostream>
#include <vector>
#include <set>
#include <string>using namespace std;// 定义 indexOf 函数，用于在源字符串中查找匹配的子串
int indexOf(const string& src, const vector<set<char>>& levels) {// 滑动匹配 levels 长度的子串for (size_t i = 0; i <= src.length() - levels.size(); ++i) {bool isFind = true;  // 标记是否找到匹配// 检查当前子串是否匹配 levels 的每一层for (size_t j = 0; j < levels.size(); ++j) {if (levels[j].find(src[i + j]) == levels[j].end()) {  // 如果字符不在当前层中isFind = false;break;}}if (isFind) {  // 如果找到匹配，返回起始位置return i;}}return -1;  // 如果未找到匹配，返回 -1
}// 定义核心函数 getResult
int getResult(const string& src, const string& tar) {vector<set<char>> levels;  // 用于存储每一层的字符集合set<char> level;           // 用于记录 [] 中的字符bool isOpen = false;       // 标记是否正在解析 [] 中的内容for (char c : tar) {if (c == '[') {isOpen = true;  // 开始解析 [] 中的内容} else if (c == ']') {isOpen = false;  // 结束解析 [] 中的内容levels.push_back(level);  // 将当前层添加到 levelslevel.clear();            // 重置当前层} else {if (isOpen) {level.insert(c);  // 将字符添加到当前层} else {levels.push_back({c});  // 将单个字符作为一层}}}// 调用 indexOf 函数查找匹配return indexOf(src, levels);
}int main() {// 输入获取string src, tar;getline(cin, src);  // 读取源字符串getline(cin, tar);  // 读取目标字符串// 调用核心函数并输出结果cout << getResult(src, tar) << endl;return 0;
}

C++ 代码讲解：

1. 头文件引入：

   • <iostream>：用于输入输出。
   • <vector>：用于动态数组。
   • <set>：用于存储每一层的字符集合。
   • <string>：用于处理字符串。

2. indexOf 函数：

   • 滑动匹配 levels 长度的子串。
   • 检查当前子串是否匹配 levels 的每一层。
   • 如果找到匹配，返回起始位置；否则返回 -1。

3. getResult 函数：

   • 将目标字符串 tar 转换为多层结构 levels。
   • 使用 set<char> 存储每一层的字符集合。
   • 调用 indexOf 函数查找匹配。

4. 主函数 main：

   • 读取用户输入的源字符串和目标字符串。
   • 调用 getResult 函数并输出结果。

---

C 语言实现

C 语言没有内置的集合和动态数组，因此需要使用数组和手动管理内存。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_LEVELS 1000  // 最大层数
#define MAX_CHARS 128    // 每层最大字符数// 定义 indexOf 函数，用于在源字符串中查找匹配的子串
int indexOf(const char* src, char levels[MAX_LEVELS][MAX_CHARS], int levelsCount) {int srcLen = strlen(src);int levelsLen = levelsCount;// 滑动匹配 levels 长度的子串for (int i = 0; i <= srcLen - levelsLen; ++i) {int isFind = 1;  // 标记是否找到匹配// 检查当前子串是否匹配 levels 的每一层for (int j = 0; j < levelsLen; ++j) {char c = src[i + j];int isInLevel = 0;// 检查字符是否在当前层中for (int k = 0; levels[j][k] != '\0'; ++k) {if (levels[j][k] == c) {isInLevel = 1;break;}}if (!isInLevel) {  // 如果字符不在当前层中isFind = 0;break;}}if (isFind) {  // 如果找到匹配，返回起始位置return i;}}return -1;  // 如果未找到匹配，返回 -1
}// 定义核心函数 getResult
int getResult(const char* src, const char* tar) {char levels[MAX_LEVELS][MAX_CHARS];  // 用于存储每一层的字符集合int levelsCount = 0;                 // 当前层数char level[MAX_CHARS];               // 用于记录 [] 中的字符int levelIndex = 0;                  // 当前层的字符索引int isOpen = 0;                      // 标记是否正在解析 [] 中的内容for (int i = 0; tar[i] != '\0'; ++i) {char c = tar[i];if (c == '[') {isOpen = 1;  // 开始解析 [] 中的内容levelIndex = 0;} else if (c == ']') {isOpen = 0;  // 结束解析 [] 中的内容level[levelIndex] = '\0';  // 结束当前层strcpy(levels[levelsCount++], level);  // 将当前层添加到 levels} else {if (isOpen) {level[levelIndex++] = c;  // 将字符添加到当前层} else {level[0] = c;  // 将单个字符作为一层level[1] = '\0';strcpy(levels[levelsCount++], level);}}}// 调用 indexOf 函数查找匹配return indexOf(src, levels, levelsCount);
}int main() {// 输入获取char src[1000], tar[1000];fgets(src, sizeof(src), stdin);  // 读取源字符串fgets(tar, sizeof(tar), stdin);  // 读取目标字符串// 去掉输入字符串末尾的换行符src[strcspn(src, "\n")] = '\0';tar[strcspn(tar, "\n")] = '\0';// 调用核心函数并输出结果printf("%d\n", getResult(src, tar));return 0;
}

C 代码讲解：

1. 头文件引入：

   • <stdio.h>：用于输入输出。
   • <stdlib.h>：用于内存管理。
   • <string.h>：用于字符串处理。

2. indexOf 函数：

   • 滑动匹配 levels 长度的子串。
   • 检查当前子串是否匹配 levels 的每一层。
   • 如果找到匹配，返回起始位置；否则返回 -1。

3. getResult 函数：

   • 将目标字符串 tar 转换为多层结构 levels。
   • 使用二维数组 levels 存储每一层的字符集合。
   • 调用 indexOf 函数查找匹配。

4. 主函数 main：

   • 读取用户输入的源字符串和目标字符串。
   • 去掉输入字符串末尾的换行符。
   • 调用 getResult 函数并输出结果。

---

示例运行：

输入：

Hello, world!
[abc]o

输出：

4

解释：

• 源字符串 src 是 "Hello, world!"。
• 目标字符串 tar 是 "[abc]o"，转换为 levels 为 [{'a', 'b', 'c'}, {'o'}]。
• 在 src 中查找匹配，发现 "o" 从索引 4 开始，因此返回 4。

输入：

Hello, world!
[xyz]o

输出：

-1

解释：

• 源字符串 src 是 "Hello, world!"。
• 目标字符串 tar 是 "[xyz]o"，转换为 levels 为 [{'x', 'y', 'z'}, {'o'}]。
• 在 src 中未找到匹配，因此返回 -1。

---

总结：

• C++ 实现：使用 std::set 和 std::vector，代码清晰，功能强大。
• C 语言实现：使用数组和手动管理内存，适合嵌入式或性能敏感场景。
• 两种实现的功能与 Python 版本一致，适合不同场景下的开发需求。

正则解法

以下是 C++ 和 C 语言的实现，并附带详细的中文注释和讲解。

---

C++ 实现

#include <iostream>
#include <string>
#include <regex> // 引入正则表达式库using namespace std;// 核心函数，用于查找目标字符串在源字符串中的起始位置
int getResult(const string& src, const string& tar) {// 使用正则表达式库的 regex_search 函数进行匹配smatch match; // 用于存储匹配结果regex pattern(tar); // 将目标字符串编译为正则表达式// 在源字符串中查找目标字符串if (regex_search(src, match, pattern)) {// 如果找到匹配，返回匹配的起始位置return match.position(); // match.position() 返回匹配的起始索引} else {// 如果未找到匹配，返回 -1return -1;}
}int main() {// 输入获取string src, tar;getline(cin, src); // 读取源字符串getline(cin, tar); // 读取目标字符串// 调用核心函数并输出结果cout << getResult(src, tar) << endl;return 0;
}

代码讲解：

1. 头文件引入：

   • <iostream>：用于输入输出。
   • <string>：用于处理字符串。
   • <regex>：C++ 的正则表达式库，用于字符串匹配。

2. 核心函数 getResult：

   • 使用 regex 类将目标字符串 tar 编译为正则表达式。
   • 使用 regex_search 函数在源字符串 src 中查找匹配。
   • 如果找到匹配，match.position() 返回匹配的起始位置；否则返回 -1。

3. 主函数 main：

   • 使用 getline 读取用户输入的两行字符串，分别存储到 src 和 tar。
   • 调用 getResult 函数并输出结果。

---

C 语言实现

C 语言没有内置的正则表达式库，因此需要借助第三方库（如 POSIX 正则表达式库 regex.h）来实现。

#include <stdio.h>
#include <string.h>
#include <regex.h> // POSIX 正则表达式库// 核心函数，用于查找目标字符串在源字符串中的起始位置
int getResult(const char* src, const char* tar) {regex_t regex; // 正则表达式对象int ret;// 编译正则表达式ret = regcomp(&regex, tar, 0);if (ret != 0) {// 如果编译失败，返回 -1return -1;}// 在源字符串中查找匹配regmatch_t match; // 用于存储匹配结果ret = regexec(&regex, src, 1, &match, 0);if (ret == 0) {// 如果找到匹配，返回匹配的起始位置return match.rm_so; // rm_so 是匹配的起始索引} else {// 如果未找到匹配，返回 -1return -1;}// 释放正则表达式对象regfree(&regex);
}int main() {// 输入获取char src[1000], tar[1000];fgets(src, sizeof(src), stdin); // 读取源字符串fgets(tar, sizeof(tar), stdin); // 读取目标字符串// 去掉输入字符串末尾的换行符src[strcspn(src, "\n")] = '\0';tar[strcspn(tar, "\n")] = '\0';// 调用核心函数并输出结果printf("%d\n", getResult(src, tar));return 0;
}

代码讲解：

1. 头文件引入：

   • <stdio.h>：用于输入输出。
   • <string.h>：用于字符串处理。
   • <regex.h>：POSIX 正则表达式库，用于字符串匹配。

2. 核心函数 getResult：

   • 使用 regcomp 函数将目标字符串 tar 编译为正则表达式。
   • 使用 regexec 函数在源字符串 src 中查找匹配。
   • 如果找到匹配，match.rm_so 返回匹配的起始位置；否则返回 -1。
   • 使用 regfree 释放正则表达式对象。

3. 主函数 main：

   • 使用 fgets 读取用户输入的两行字符串，分别存储到 src 和 tar。
   • 去掉输入字符串末尾的换行符。
   • 调用 getResult 函数并输出结果。

---

示例运行：

输入：

Hello, world!
world

输出：

7

解释：

• 源字符串 src 是 "Hello, world!"。
• 目标字符串 tar 是 "world"。
• 在 src 中查找 tar，发现 "world" 从索引 7 开始，因此返回 7。

输入：

Hello, world!
java

输出：

-1

解释：

• 源字符串 src 是 "Hello, world!"。
• 目标字符串 tar 是 "java"。
• 在 src 中未找到 "java"，因此返回 -1。

---

总结：

• C++ 实现：使用 C++ 标准库的 <regex>，代码简洁，功能强大。
• C 语言实现：使用 POSIX 正则表达式库 <regex.h>，需要手动管理正则表达式对象的编译和释放。
• 两种实现的功能与 Python 版本一致，适合不同场景下的开发需求。

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

1. 机试是进入技术面的第一关：
   华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。

2. 技术面试需要手撕代码：
   技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。

3. 入职后的可信考试：
   入职华为后，还需要通过“可信考试”。可信考试分为三个等级：

   • 入门级：主要考察基础算法与编程能力。
   • 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
   • 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

1. 关注历年真题：

   • 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
   • 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。

2. 适应新题目：

   • E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
   • 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。

3. 掌握常见算法：
   华为OD考试通常涉及以下算法和数据结构：

   • 排序算法（快速排序、归并排序等）
   • 动态规划（背包问题、最长公共子序列等）
   • 贪心算法
   • 栈、队列、链表的操作
   • 图论（最短路径、最小生成树等）
   • 滑动窗口、双指针算法

4. 保持编程规范：

   • 注重代码的可读性和注释的清晰度。
   • 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

1. 官方参考：

   • 华为招聘官网或相关的招聘平台会有一些参考信息。
   • 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。

2. 加入刷题社区：

   • 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
   • 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。

3. 寻找系统性的教程：

   • 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
   • 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

1. 本地编写代码

   • 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。

2. 调整心态，保持冷静

   • 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。

3. 输入输出完整性

   • 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。

4. 快捷键使用

   • 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
   • 避免使用 Ctrl+S，以免触发浏览器的保存功能。

5. 浏览器要求

   • 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。

6. 交卷相关

   • 答题前，务必仔细查看题目示例，避免遗漏要求。
   • 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
   • 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。

7. 时间和分数安排

   • 总时间：150 分钟；总分：400 分。
   • 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。

8. 考试环境准备

   • 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
   • 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。

9. 技术问题处理

   • 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
   • 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利，取得理想成绩！