資料結構
網路
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 多次瀏覽
廣告