If a string is matched to any filter, it is in the black list, otherwise not.
Design a data structure and implement following two functions.addFilter(filter)
isInBlackList(string)filters are in the form of
“a*b”
“abc”
“aa*b”
having at most one star, which matches 0 or more chars.
ワイルドカードを含む探索を再帰を使って実装してみます。
文字列: abc
パターン: a*c
がマッチするかは最初の文字を比較します
文字列: [a]bc
パターン: [a]*c
不一致ならfalse、一致するなら最初の1文字を取り除いて
文字列: bc
パターン: *c
がマッチするか確かめればよいということです。
ポインタを2つ用意します。マッチするか確かめる文字列のポインタと、パターンのポインタです。
1文字ずつ読み進めていきますが、もし一致しないものが見つかればそこでfalseを返します。
パターンを最後まで読み終えてしまった場合、検証する文字列も終わりならtrue, 違うならfalseを返します。
最後に*に当たった場合は
- 0文字マッチする場合→単に*を飛ばして残りがマッチするか再帰
- 1文字以上マッチする場合→テキストを1文字飛ばして再帰、+1する都合上テキストの終端を確認
bool match( const char *text, const char *pattern ) { while(true) { if( *pattern == '\0' ) { if( *text == '\0' ) return true; else return false; } if( *pattern == '*' ) { bool a = match( text, pattern + 1 ); bool b = *text != '\0' && match( text + 1, pattern ); return a || b; } if( *text == *pattern ) { text++; pattern++; } else { return false; } } return false; }
任意の文字にマッチする?も探すのなら、テキストとパターンを1個進めて再帰も入れればOK。
コード全体は
vector<string> filter; bool match( const char *text, const char *pattern ) { while(true) { if( *pattern == '\0' ) { if( *text == '\0' ) return true; else return false; } if( *pattern == '*' ) { bool a = match( text, pattern + 1 ); bool b = *text != '\0' && match( text + 1, pattern ); return a || b; } if( *text == *pattern ) { text++; pattern++; } else { return false; } } return false; } void addFilter(const string &f) { filter.push_back(f); } bool isInBlackList(const string &text) { bool result = false; for( auto f: filter ) { if( match( text.c_str(), f.c_str() ) == true ) result = true; } return result; } int main() { addFilter("a*b"); addFilter("aa*b"); addFilter("abc"); addFilter("abdr*"); // true assert( isInBlackList("accb") == true ); assert( isInBlackList("ab") == true ); assert( isInBlackList("aaxvfbb") == true ); assert( isInBlackList("abc") == true ); assert( isInBlackList("abdreee") == true ); // false assert( isInBlackList("ax") == false ); assert( isInBlackList("aa") == false ); assert( isInBlackList("bb") == false ); }
最近のコメント