通配符模式匹配

假设我们有一个字符串和一个模式，我们需要将字符串与模式进行比较，以确定模式是否与字符串匹配。我们这里寻找的是完全匹配，而不是部分匹配。给定的文本和通配符模式实现了通配符模式匹配算法来查找匹配。该算法查找完全匹配，而不是部分匹配。

通配符模式包含以下两个特殊字符：

• '?': 代表任何单个字符
• '*': 代表 0 个或任意多个字符序列。

让我们通过例子来理解。

示例 1：假设模式是 (a * b)

模式：a * b

如果字符串是“ab”

模式以“a”字符开头，以“b”字符结尾。在“a”和“b”之间，我们可以使用任何字符。由于字符串以“a”开头，以“b”结尾，并且在“a”和“b”之间不包含任何字符；因此，该字符串与模式完全匹配。

如果字符串是“aab”

字符串以“a”开头，以“b”结尾，并在“a”和“b”之间包含“a”字符。根据指定的模式，我们可以在“a”和“b”之间使用任何字符；因此，上述字符串与指定的模式完全匹配。

如果字符串是“a”

由于字符串不以字符“b”结尾；因此，上述字符串与指定的模式不匹配。所以，返回 false 值。

如果字符串是“abc”

由于字符串以“c”字符结尾而不是“b”字符；因此，该字符串与指定的模式不完全匹配。所以，返回 false 值。

模式是“a ? b”

上述模式指定字符串应以“a”开头，以“b”结尾。字符串在“a”和“b”之间应正好包含一个字符。

如果字符串是“aab”

由于字符串以“a”开头，以“b”结尾，并且在“a”和“b”之间正好包含一个字符；因此，该字符串完全满足指定模式。

如果字符串是“ab”

由于字符串以“a”开头，以“b”结尾，但“a”和“b”之间不包含任何字符，因此字符串与模式不完全匹配。返回 false 值。

模式是：x ? y * z

上述模式指定“x”和“y”之间可以有任何单个字符，“y”和“z”之间可以有 0 个或任意多个字符序列。

如果字符串是“xayz”

在给定的字符串中，“x”和“y”之间只有一个字符，而“y”和“z”之间没有单个字符；因此，该字符串与模式完全匹配。

如果字符串是“xyz”

在给定的字符串中，“x”和“y”之间没有单个字符；因此，给定的字符串与指定的模式不完全匹配。

这里我们将使用动态规划方法来解决问题。

在上述方程中，“T”是二维数组，T[i][j] 是字符串中从 0 到 i 的子字符串，从 0 到 j 代表模式。

让我们以表格形式来理解。

当 i=0，j = 0 时

当 i=0，j = (0 到 5) 时

当 i=1，j=0 时

当 i=1，j=1 时

因为 T[i] = =T[j]，即 x==x；因此，第一个条件得到满足。根据第一个条件，我们将取 T[i-1][j-1]，即对角线值。所以，T[1][1] = T，如上表所示。

当 i=1，j=2 时

在这种情况下，字符串是“x”，模式是“x ?”。T[i-1][j-1] 等于“x”，所以返回 false 值。

当 i=1，j=3 时

因为“x”不等于“y”，所以我们在 T[1][3] 处得到 false。

当 i=1，j=4 时

正如我们在上表中观察到的那样，“*”是模式。根据条件 3，我们将查看左边和顶部的值。由于两侧的值都是 false；因此，T[1][4] 的值也是 false。

当 i=1，j=5 时

因为 T[1] 的值不等于 T[5]，即 x!=z；因此，T[1][5] 的值也是 false。

当 i=2，j=1 时

现在字符串是“xa”，模式是“x”。由于两者不相同；因此，T[2][1] 的值为 false。

当 i=2，j=2 时

现在字符串是“xa”，模式是“x?”。当我们将“xa”与“x?”进行比较时，“x”与“x”匹配，“?”表示“x”字符之后正好有一个字符。在字符串“xa”中，“a”字符在“x”之后。因此，该字符串与模式完全匹配。

当 i=2，j=3 时

正如我们在上表中观察到的那样，T[2] 是“a”，T[3] = “y”；由于这两个字符都不同，因此 T[2][3] 的值为 false。

当 i=2，j=4 时

由于模式是“*”，根据条件 2，我们将查看左边和顶部的值。由于两侧的值都是 false；因此，T[2][4] 的值也是 false。

当 i=2，j=5 时

由于 T[i] 的值不等于 T[j]，即 a !=z；因此，T[2][5] 的值等于 false。

当 i=3，j=1 时

T[3] 的值为“y”，T[1] 的值为“x”。由于两个值都不同，因此 T[3][1] 的值将是 false。

当 i=3，j=2 时

这里，模式是“x?”，字符串是“xay”。“?”与“y”匹配，但“xa”和“x”不匹配，所以我们考虑对角线值，即 false。因此，T[3][2] 的值也将是 false。

当 i=3，j=3 时

在这种情况下，模式是“x?y”，字符串是“xay”。当我们比较模式和字符串时，“x”与“x”匹配，“?”与“a”匹配，并且“y”与“y”匹配。因此，我们可以说字符串与模式完全匹配，T[3][3] 的值为 true。

当 i=3，j=4 时

在这种情况下，字符串是“xay”，模式是“x?y*”。“*”匹配 0 个或多个字符序列。我们查看左边和顶部的值。由于左边的值是 true；因此，T[3][4] 的值是 true。

当 i=3，j=5 时

由于“y”与“z”不匹配，因此 T[3][5] 的值将是 false。

当 i=4，j=1 时

由于“l”与“x”不匹配，因此 T[3][1] 的值将是 false。

当 i=4，j=2 时

现在模式是“?”，所以我们将考虑对角线值。对角线值为 false，所以 T[3][2] 的值也将是 false。

当 i=4，j=3 时

这里，T[3] = ‘l’ 且 T[3] = ‘y’。由于这两个字符都不同，因此 T[3][3] 的值将是 false。

当 i=4，j=4 时

这里，T[j] = ‘*’。在这种情况下，我们将查看左边和顶部的值。由于顶部的值是 true，因此 T[3][4] 的值也将是 true。

当 i=4，j=5 时

T[4] 的值为“l”，T[5] 的值为“z”。由于“l”不等于“z”，因此 T[4][5] 的值将是 false。

当 i=5，j=1 时

T[5] 的值为“m”，T[1] 的值为“x”。由于“m”不等于“x”，因此 T[5][1] 的值将是 false。

当 i=5，j=2 时

在这种情况下，pattern[j] 是“?”，所以我们将考虑对角线值。由于对角线值为“false”，因此 T[5][2] 的值也将是 false。

当 i=5，j=3 时

在这种情况下，T[5] 的值为“m”，T[3] 的值为“y”。由于两个值都不同，因此 T[5][3] 的值将是 false。

当 i=5，j=4 时

这里，pattern[j] 是“*”。我们将查看左边和右边的值。顶部的值是 false，所以 T[5][4] 的值也将是 true。

当 i=5，j=5 时

T[5] 的值为“m”，T[5] 的值为“z”。由于两个值都不同，因此 T[5][5] 的值将是 false。

同样，我们将对最后一行执行操作。表格可以表示为

在最后一行和最后一列，我们得到 true 值。因此，最终值为 true，所以给定的字符串与模式完全匹配。

C++ 中通配符模式匹配的实现

输出