通配符模式匹配
针对此问题，给出了一个主字符串和另一种通配符模式。在该算法中，它将检查通配符模式是否与主要文本匹配。
通配符模式可以包含字母或“*”或“？”符号。'？'用于匹配单个字符，“*”用于匹配字符序列，包括空格。
当字符为“*”时：我们可以忽略星号，然后移动以检查模式中的下一个字符。
当下一个字符为“？”时，我们可以仅忽略文本中的当前字符，并检查模式和文本中的下一个字符。
当图案字符不是'*'和'？'时，则如果图案和文本的当前字符匹配，则仅进一步移动。
输入输出
Input: The main string and the wildcard pattern. Main String “Algorithm” Pattern “A*it?m” Output: The 模式匹配。
算法
wildcardMatch(text, pattern)
输入：主要文字和图案。
输出： 当通配符模式与主要文本匹配时为True。
Begin
n := length of the text
m := length of pattern
if m = 0, then
return 0 if n = 0, otherwise return 1
i := 0, j := 0
while i < n, do
if text[i] == pattern[i], then
increase i by 1
increase j by 1
else if j < m and pattern[j] is ? mark, then
increase i by 1
increase j by 1
else if j < m and pattern[j] is * symbol, then
textPointer := i
patPointer := j
increase j by 1
else if patPointer is already updated, then
j := patPointer + 1
i := textPinter + 1
increase textPointer by 1
else
return false
done
while j < m and pattern[j] = * symbol, do
increase j by 1
done
if j = m, then
return true
return false
End示例
#include<iostream>
using namespace std;
bool wildcardMatch(string text, string pattern) {
int n = text.size();
int m = pattern.size();
if (m == 0) //when pattern is empty
return (n == 0);
int i = 0, j = 0, textPointer = -1, pattPointer = -1;
while (i < n) {
if (text[i] == pattern[j]) { //matching text and pattern characters
i++;
j++;
}else if (j < m && pattern[j] == '?') { //as ? used for one character
i++;
j++;
}else if (j < m && pattern[j] == '*') { //as * used for one or more character
textPointer = i;
pattPointer = j;
j++;
}else if (pattPointer != -1) {
j = pattPointer + 1;
i = textPointer + 1;
textPointer++;
}else
return false;
}
while (j < m && pattern[j] == '*') {
j++; //j will increase when wildcard is *
}
if (j == m) { //check whether pattern is finished or not
return true;
}
return false;
}
int main() {
string text;
string pattern;
cout << "Enter Text: "; cin >> text;
cout << "Enter wildcard pattern: "; cin >> pattern;
if (wildcardMatch(text, pattern))
cout << "模式匹配。" << endl;
else
cout << "Pattern is not matched" << endl;
}输出结果
Enter Text: Algorithm Enter wildcard pattern: A*it?m 模式匹配。