数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理
社会学
时尚学
法学通配符模式匹配
为了解决这个问题，给出了一条主要字符串和另一个通配符模式。此算法将检查通配符模式是否与主文本匹配。
通配符模式可能包含字母或 ‘*’ 或 ‘?’ 符号。‘?’ 用于匹配单个字符，而 ‘*’ 用于匹配一系列字符，包括空格。
当字符为‘*’时：我们可以忽略星号字符，然后检查模式中的下一个字符。
当下一个字符为‘?’时，我们则只忽略文本中的当前字符，然后检查模式和文本中的下一个字符。
当模式字符不为‘*’和‘?’时，如果模式和文本的当前字符匹配，则只能进一步移动。
输入和输出
Input: The main string and the wildcard pattern. Main String “Algorithm” Pattern “A*it?m” Output: The pattern matched.
算法
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 << "Pattern Matched." << endl;
else
cout << "Pattern is not matched" << endl;
}输出
Enter Text: Algorithm Enter wildcard pattern: A*it?m Pattern Matched.
更新于：17-Jun-2020
1000 多次浏览
广告