資料結構
網路
關係資料庫
作業系統
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-6-2020
1 千+瀏覽
廣告