C++ 中的不区分大小写搜索

在 C++ 中执行不区分大小写的搜索需要先将字符转换为一致的大小写（大写或小写），然后再进行比较。这可以确保字母大小写的差异不会影响搜索结果。

在执行区分大小写的搜索时，比较会考虑字母的精确大小写（例如，“A” ≠“a”）。相反，不区分大小写的搜索会忽略字母的大小写，将“A”和“a”视为相等。

带示例的说明

假设您有一个源 字符串 和一个搜索词

• 源字符串：“Hello World”
• 搜索词：“world”

要执行不区分大小写的搜索

将“Hello World”和“world”都转换为小写

• “hello world”
• “world”

使用 std::string::find 在小写源字符串中查找小写的搜索词。

方法 1：简单方法

示例

输出

 
Enter the source string: Hello World
Enter the search term: WORLD
The search term "WORLD" was not found in the source string.   

说明

步骤 1：接收用户输入

程序首先要求用户输入两个字符串

• 源字符串： 这是我们要搜索子字符串的较大文本。
• 搜索词： 这是我们要在此源字符串中查找的文本。

这两种输入都使用允许文本中包含空格的方法来收集，以确保输入的灵活性。

步骤 2：创建搜索逻辑函数

为了使代码可重用和模块化，实际的搜索逻辑被写入一个单独的函数中。这个 函数 接受两个字符串作为输入

• 执行搜索的源字符串。
• 要查找的目标字符串（或搜索词）。

这种关注点分离确保了搜索逻辑可以在程序的其他部分需要时重用。

步骤 3：标准化两个字符串

不区分大小写的搜索要求忽略字母的大小写。例如，“World”和“world”应该被视为相同。为了实现这一点

创建源字符串和搜索字符串的副本，以保留它们的原始形式。

将两个字符串中的所有字符都转换为小写。

• 使用一个处理小写转换的函数单独转换每个字符。
• 这确保了两个字符串中的所有字符都处于统一的大小写状态，使比较更加直接。

步骤 4：执行搜索

将两个字符串都转换为小写后

• 程序使用标准的搜索方法在源字符串中搜索目标字符串。这会检查目标字符串中的字符序列是否与源字符串的任何部分匹配。
• 使用的搜索方法将在找到目标字符串时返回第一个匹配项的位置。如果未找到匹配项，它将用特殊值指示失败。

步骤 5：返回搜索结果

然后函数评估是否找到了目标字符串

• 如果目标字符串存在于源字符串中，则函数返回 true。
• 如果未找到目标字符串，则函数返回 false。

步骤 6：向用户显示结果

回到程序的主体部分

使用输入字符串调用该函数，并检查结果。

根据结果

• 如果为 true，则显示一条消息，指示在源字符串中找到了搜索词。
• 如果为 false，则显示一条消息，指示未找到搜索词。

复杂度分析

时间复杂度

复制字符串

• 复制源字符串和目标字符串分别需要 O(n) 和 O(m) 的时间，其中 n 是源字符串的长度，m 是搜索词的长度。

转换为小写

• 将两个字符串转换为小写需要 O(n)（对于源字符串）和 O(m)（对于搜索词）。

搜索子字符串

• 使用 std::string::find 的最坏情况时间复杂度为 O(n⋅m)，因为源字符串中的每个字符都可能与搜索词中的每个字符进行比较。

总时间复杂度

综合来看，总时间复杂度为 O(n+m+n⋅m)。在大多数情况下，O(n⋅m) 项是最显著的。

空间复杂度

额外字符串

• 两个新字符串（用于源字符串和小写搜索词）分别需要 O(n) 和 O(m) 的空间。

临时变量

• 用于字符转换的临时空间非常小，对空间复杂度影响不大。

总空间复杂度

由于存储了转换后的字符串，空间复杂度为 O(n+m)。

方法 2：直接不区分大小写比较

此方法逐个比较源字符串和目标字符串的每个字符，在过程中仅将参与比较的字符转换为相同的大小写（大写或小写）。它避免了进行全字符串转换的需要，并在空间方面更有效。

程序

输出

 
Enter the source string: Hello world
Enter the search term HELLO
The search term "HELLO" was found in the source string.   

说明

步骤 1：接受输入

程序首先要求用户输入两个字符串

源字符串： 这是我们要搜索目标字符串的字符串。

搜索词： 这是我们要在此源字符串中查找的子字符串。

这些输入使用 std::getline 收集，它允许用户输入多词字符串，包括空格。

步骤 2：开始搜索

搜索的核心逻辑封装在一个函数中。该函数接受两个参数

• 源字符串（较大文本）。
• 搜索词（我们要在此源字符串中找到的子字符串）。

该函数的目标是如果目标字符串存在于源字符串中则返回 true，如果不存在则返回 false。

步骤 3：遍历源字符串

下一步是遍历源字符串。思路是检查源字符串中搜索词可能开始的每个可能位置，然后比较字符。

• 对于源字符串中的每个位置，我们将比较与搜索词长度相同的子字符串。
• 循环确保我们只检查搜索词可以容纳在源字符串中的有效位置。

步骤 4：比较每个子字符串

对于源字符串中的每个潜在起始位置，程序会将该位置开始的子字符串与搜索词进行比较

• 比较是逐个字符进行的。

但是，为了使其不区分大小写，我们不直接比较字符。相反，在比较之前，将源字符串和搜索字符串中的两个字符都转换为相同的大小写（大写或小写）。这确保了像“A”和“a”或“b”和“B”这样的字符被视为相等。

步骤 5：检查匹配项

如果源子字符串中的每个字符都与搜索词中的相应字符匹配（以不区分大小写的方式），我们可以得出结论，我们在源字符串中找到了搜索词。在这种情况下，函数会立即返回 true，表示成功匹配。

如果即使有一个字符不匹配（即使是不区分大小写的），函数也会将比较标记为失败，并继续检查源字符串中的下一个可能的起始位置。

步骤 6：处理不匹配项

如果程序在源字符串中检查完所有可能的起始位置而没有找到匹配项，则返回 false。这意味着目标字符串不存在于源字符串中。

步骤 7：输出结果

最后，搜索结果（目标是否找到）将在程序的主体部分显示给用户

• 如果返回 true，程序将打印一条成功消息，指示找到了搜索词。
• 如果返回 false，它将打印一条失败消息，指出未找到搜索词。

复杂度分析

时间复杂度

• 遍历源字符串： 程序遍历源字符串，检查搜索词的每个可能起始位置。这给出了 O(n)，其中 n 是源字符串的长度。
• 字符比较： 对于每个起始位置，我们将源子字符串的每个字符与目标字符串进行比较。此比较需要 O(m) 时间，其中 m 是目标字符串的长度。
• 最坏情况时间复杂度为 O(n⋅m)，因为在最坏情况下，我们可能需要将源字符串中的每个字符与目标字符串中的每个字符进行比较。

空间复杂度

• 恒定空间： 该算法仅使用少量变量来存储字符串中的当前位置并执行比较。不创建任何额外的数组或字符串等数据结构。
• 空间复杂度为 O(1)，因为空间使用不会随输入的大小而增长。

优点

空间利用率

• 这种方法在空间上非常高效，因为它不需要创建任何额外的字符串或 数据结构。它仅使用少量 变量 进行索引和比较，使得空间复杂度为恒定的 O(1)。

无完整字符串转换

• 与其他方法将整个源字符串和目标字符串转换为小写或大写不同，此方法会即时执行不区分大小写的比较。这意味着无需创建字符串的副本，从而节省了时间和空间。

简单直接

• 该算法非常简单易于实现。它直接比较字符，并通过在比较过程中转换字符来确保不区分大小写，从而避免了复杂的逻辑。

对小输入高效

• 对于较小的字符串或较短的搜索词，此方法可以非常高效，因为它避免了创建字符串的额外副本或完全转换它们的开销。

易于理解和实现

• 该方法简单易懂且易于实现，使其成为初学者或需要快速解决方案的用户的不错选择。没有复杂的概念，只有基本的循环和字符串操作，使得任何学习 C++ 的人都容易上手。

缺点

最坏情况时间复杂度

• 最坏情况下的 O(n⋅m) 时间复杂度对于大型输入大小来说可能会很慢。对于非常大的源字符串和搜索词，此方法可能不是最优的。

重复的大小写转换

• 由于字符在每次比较期间都会转换为小写（或大写），因此转换步骤可能会重复，尤其是在目标字符串较短或源字符串较大的情况下。与预先处理字符串一次的其他方法相比，这会增加开销。

对大型输入的优化有限

• 此方法没有利用 Boyer-Moore 或 Knuth-Morris-Pratt 等高级优化技术，这些技术可以在实际场景中降低时间复杂度。因此，对于大型数据集或频繁搜索，此方法可能无法很好地扩展。

无法并行化

• 搜索过程本质上是顺序的，这意味着它不容易并行化。对于需要处理非常大的文本或高频搜索的应用程序，这可能是一个限制。

有限的案例处理

• 虽然此方法在不区分大小写的搜索方面效果很好，但它不处理其他复杂性，例如特定区域设置的大小写折叠或其他字符编码（例如，特殊字符或带重音的字母）。对于更高级的文本处理，此方法可能需要额外的改进才能处理不同的语言或字符集。