面试题：C++ 自定义字符串函数的实现与优化

def myStrFind(main_str, sub_str):
    len_main = len(main_str)
    len_sub = len(sub_str)
    for i in range(len_main - len_sub + 1):
        if main_str[i:i+len_sub] == sub_str:
            return i
    return -1


# 优化策略：
# 1. 提前计算主字符串和子字符串的长度，避免在每次循环中重复计算。
# 2. 循环的终止条件设置为 len_main - len_sub + 1，减少不必要的循环次数。

# 时间复杂度分析：
# 1. 最坏情况：子字符串不存在于主字符串中，或者子字符串在主字符串的最后位置出现。此时需要遍历主字符串中所有可能的起始位置，时间复杂度为 O(n * m)，其中 n 是主字符串的长度，m 是子字符串的长度。
# 2. 最好情况：子字符串在主字符串的开头位置出现，此时只需要比较一次，时间复杂度为 O(m)，其中 m 是子字符串的长度。

public class StringFinder {
    public static int myStrFind(String mainStr, String subStr) {
        int lenMain = mainStr.length();
        int lenSub = subStr.length();
        for (int i = 0; i <= lenMain - lenSub; i++) {
            if (mainStr.substring(i, i + lenSub).equals(subStr)) {
                return i;
            }
        }
        return -1;
    }
}
// 优化策略：
// 1. 提前获取主字符串和子字符串的长度，避免在循环中多次调用 length 方法。
// 2. 循环的终止条件设置为 lenMain - lenSub，减少不必要的循环。

// 时间复杂度分析：
// 1. 最坏情况：子字符串不存在于主字符串中，或者子字符串在主字符串的最后位置出现。此时需要遍历主字符串中所有可能的起始位置，时间复杂度为 O(n * m)，其中 n 是主字符串的长度，m 是子字符串的长度。
// 2. 最好情况：子字符串在主字符串的开头位置出现，此时只需要比较一次，时间复杂度为 O(m)，其中 m 是子字符串的长度。

#include <iostream>
#include <string>

int myStrFind(const std::string& mainStr, const std::string& subStr) {
    size_t lenMain = mainStr.length();
    size_t lenSub = subStr.length();
    for (size_t i = 0; i <= lenMain - lenSub; ++i) {
        if (mainStr.substr(i, lenSub) == subStr) {
            return static_cast<int>(i);
        }
    }
    return -1;
}

// 优化策略：
// 1. 提前计算主字符串和子字符串的长度，避免在每次循环中重复调用 length 方法。
// 2. 循环的终止条件设置为 lenMain - lenSub，减少不必要的循环。

// 时间复杂度分析：
// 1. 最坏情况：子字符串不存在于主字符串中，或者子字符串在主字符串的最后位置出现。此时需要遍历主字符串中所有可能的起始位置，时间复杂度为 O(n * m)，其中 n 是主字符串的长度，m 是子字符串的长度。
// 2. 最好情况：子字符串在主字符串的开头位置出现，此时只需要比较一次，时间复杂度为 O(m)，其中 m 是子字符串的长度。

星途面试题库

面试题：C++ 自定义字符串函数的实现与优化

知识考点

面试题答案