C++ 不包含通配符*和.的情况下检查给定模式是否存在于给定字符串中或不存在

在计算机科学和编程中，检查给定模式是否存在于给定字符串中或不存在，包括通配符*和.是一个常见的问题。在这个问题中，我们会给出一个字符串（文本）和一个模式，模式中可以包含通配符字符*和.，我们需要检查模式是否与文本匹配。这个问题在很多应用中都会遇到，比如搜索引擎、文件系统和网络协议。

在本教程中，我们将讨论使用C++解决这个问题的一个简单高效的方法。我们将从解释问题陈述和约束开始，然后逐步给出解决方案的指南。我们还将提供一个实现我们解决方案的示例C++代码，并讨论其时间和空间复杂度。所以让我们开始吧！

问题陈述

目标是确定给定的模式，包含通配符字符“*”和“.”，是否与给定的文本字符串匹配。模式和文本的长度分别为M和N。如果模式匹配文本，则输出“Yes”。否则，输出“No”。

需要注意的是，“*”字符匹配其前面那个字符的零个或多个出现，“.”字符匹配任意单个字符。

示例1

输入

Text: "hello world"; Pattern: "h*llo w•rld"

输出

Yes

说明：在这个例子中，文本是”hello world”，模式是”hllo w·rld”。模式中的”字符匹配它前面的字符的零个或多个出现。因此，它匹配文本中的’h’。’·’字符匹配任何一个字符，所以它匹配文本中的空格字符。模式还匹配文本中的’o’和’w’字符。因此，模式匹配文本，输出结果是”Yes”。

示例例子2

输入

Text: "cat"; Pattern: "c*t•"

输出

No

说明：在此示例中，文本为”cat”，模式为”ct•”。模式中的”字符匹配与其之前的字符立即重复零次或更多次。因此，它与文本中的’c’匹配。’•’字符匹配任何单个字符，因此它与文本中的’a’字符匹配。但是，模式不匹配文本中的最后一个’t’字符，因为没有’•’字符与其匹配。因此，模式不匹配文本，输出为” No”。

算法

1.初始化矩阵dp，其维度为(n+1)×(m+1)，其中dp[i][j]表示文本子字符串至索引i是否与模式子字符串至索引j相匹配。

2.将dp[0][0]设置为true，因为空文本和空模式始终匹配。

3.迭代遍历模式中的每个字符，从索引1到m：

如果当前字符是”，则将dp[0][i]设置为dp[0][i-1]，表示”可以与空子字符串匹配。

4.迭代遍历文本中的每个字符，从索引1到n：

对于模式中的每个字符，从索引1到m：
- 如果文本和模式中当前位置的字符相同，或者模式字符为’?’，则将dp[i][j]设置为dp[i-1][j-1]，因为当前字符匹配。
- 如果模式字符为”，则将dp[i][j]设置为dp[i][j-1]（表示”与空子字符串匹配）或dp[i-1][j]（表示’*’与当前文本字符匹配）。
- 否则，将dp[i][j]设置为false。

5.最终结果存储在dp[n][m]中，该结果指示整个文本是否与整个模式匹配。

该算法使用动态规划方法构建矩阵，对模式中的每个字符考虑三种可能的情况：匹配文本中的字符、匹配’?’或匹配’*’。如果整个文本与整个模式匹配，则算法返回true，否则返回false。

示例

使用C++实现上述算法

以下C++程序旨在确定给定的文本是否与包含’*’和’?’符号的模式匹配。该算法利用动态规划来构建一个矩阵dp[n+1][m+1]，其中n是文本的长度，m是模式的长度。

输入

"hello world"; string pattern = "h*llo w?rld"; ****

输出

Yes

示例

#include <iostream>
#include <vector>
bool isMatch(const std::string& text, const std::string& pattern) {
   int n = text.length();
   int m = pattern.length();
   std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(m + 1, false));
   dp[0][0] = true;
   for (int i = 1; i <= m; i++) {
      if (pattern[i - 1] == '*') {
         dp[0][i] = dp[0][i - 1];
      }
   }
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
         if (text[i - 1] == pattern[j - 1] || pattern[j - 1] == '?') {
            dp[i][j] = dp[i - 1][j - 1];
         } else if (pattern[j - 1] == '*') {
            dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
         } else {
            dp[i][j] = false;
         }
      }
   }
   return dp[n][m];
}
int main() {
   std::string text = "hello world";
   std::string pattern = "h*llo w?rld";
   if (isMatch(text, pattern)) {
      std::cout << "Yes\n";
   } else {
      std::cout << "No\n";
   }
   return 0;
}

输出结果

Yes

结论

总之，提供的程序使用动态规划实现了一种模式匹配算法。它确定给定的文本是否与包含通配符“*”和“?”符号的模式匹配。通过构建矩阵并迭代比较字符，该算法有效地评估匹配条件。独特的方法确保准确的模式匹配结果，允许进行灵活的文本比较。该程序在字符串匹配、文本处理和数据分析等各种应用中作为有价值的工具。其效率和可靠性使其成为处理模式匹配任务时的可靠选择。