子串检查

子字符串检查是计算机科学和字符串操作中的典型问题，即字符串包含。所需的是识别特定字符串（子字符串）是否是较大字符串（主字符串）的组成部分。你必须确定子字符串是否出现在主字符串中。

简单来说，给定两个字符串 S1 和 S2，你必须检查 S1 是否包含 S2 作为子字符串。如果是子字符串，返回 true，否则返回 false。

例如

字符串 S1: "growing"

字符串 S2: "grow"

结果：子字符串 S2 "grow" 存在于主字符串 S1 中。

根据所需的效率和编程语言，这个问题有多种解决方法。以下是查找子字符串的三种典型方法

朴素方法

使用嵌套循环是检查子字符串的一种快速简单的方法。内层循环确定当前位置开始的字符是否与子字符串中的字符匹配，而外层循环遍历主字符串的每个字符。如果每个字符都匹配，则子字符串存在于主字符串中。

算法

• 首先构建一个主字符串和你正在其中查找的子字符串。
• 主字符串是“The quick brown fox jumps over the lazy dog”。子字符串是“fox”。
• 设置变量以跟踪主字符串 (n) 和子字符串 (m) 的长度。
• “The swift brown fox jumps over the lazy hound” 有 44 个单词长。（“fox” 的长度）= m
• 为了确保有足够的字符来匹配整个子字符串，设置一个外层循环，该循环遍历主字符串中直到 (n - m) 索引的字符。
• 在外层循环内创建一个内层循环，该循环遍历子字符串的字符。
• 比较主字符串和子字符串中的字符。如果存在不匹配，则跳出内层循环并移至主字符串中的下一个索引。
• 如果内层循环成功结束且没有不匹配，则在主字符串中已找到整个子字符串。返回 true。
• 如果外层循环结束而没有发现匹配的子字符串，则返回 false。

在 JAVA 中

输出

Substring is present: True

Java SubstringCheck 类的 substring 方法用于检查给定字符串 (S2) 是否是另一个字符串 (S1) 的子字符串。该函数通过使用两个嵌套循环比较两个字符串中的字符，采用了一种简单的方法。当发现不匹配时，内层循环会前进到 S1 中的下一个位置。内层循环必须成功完成而没有不匹配，方法才能返回 true，这表示 S2 作为子字符串存在于 S1 中。当 S1="growing" 和 S2="grow" 用于在主方法中测试该函数时，结果是“子字符串存在：true”，表明“grow”是“growing”的子字符串。然而，由于其时间复杂度 O(n * m)，这种方法对于较长的字符串效率低下。

在 Python 中

输出

Substring is present: True

Python 代码中使用的逻辑与 Java 实现相同。SubstringCheck 类的静态函数 substring 使用一种粗略的方式来确定 S2 是否是 S1 的子字符串。在这种情况下，当在主块中使用 S1="growing" 和 S2="grow" 测试该方法时，会打印“子字符串存在：True”，因为“grow”是“growing”的子字符串。此实现的时间复杂度仍然是 O(n * m)。

在 C++ 中

输出

Substring is present: True

上述 C++ 代码使用 SubstringCheck 类的静态函数 substring 来确定 S2 是否是 S1 的子字符串。在主函数中，使用此技术演示了在主字符串“growing”中检查子字符串“grow”。由于结果为 true，表明它存在，因此将子字符串打印为输出。

内置字符串函数

为了搜索子字符串，大多数计算机语言都有内置的字符串函数。

Python

在 Python 中，使用 "find()" 方法或 "in" 关键字来搜索子字符串

输出

Substring is present.

该代码使用 Python 关键字检查子字符串 "how" 是否存在于主字符串 "Hello, how are you?" 中。由于子字符串 "how" 存在于主字符串中，当条件 if substring in main_string: 评估为 True 时，将打印语句 "Substring is present."。如果子字符串不存在于主字符串中，则会调用 else 块并打印 "Substring is not present."。但是，在这种情况下，子字符串是存在的。因此，运行第一个块，产生指定的输出。

在 Java 中

Java 中 String 类的 "contains" 方法可用于执行相同的子字符串检查。下面提供了子字符串检查的 Java 代码

输出

Substring is present.

此 Java 代码使用 String 类方法来确定子字符串“how”是否存在于主字符串“Hello, how are you?”中。语句“mainString.contains(substring)”评估为 true，因为子字符串包含在主字符串中，打印“Substring is present.”。如果子字符串从主字符串中缺失，则会显示消息“Substring is not present.”。但是，在这种情况下，子字符串是存在的。因此，输出打印第一条消息。

在 C++ 中

在 C++ 中，你可以使用 std::string 类的 find 方法来执行子字符串检查。这是子字符串检查的 C++ 代码

输出

Substring is present.

此 C++ 代码使用 std::string 类的 find 函数检查子字符串 "how" 是否包含在主字符串 "Hello, how are you?" 中。如果找不到子字符串，find 方法返回 std::string::npos，或者子字符串第一个实例的起始索引。如果返回的索引不等于 std::string::npos，则打印消息 "Substring is present."，表示子字符串存在。否则，如果未找到子字符串，则打印 "Substring is not present." 作为输出。但是，子字符串存在，导致打印初始消息。