通配符字符串匹配递归函数

Question

我有点不知道如何将字符串与通配符字符串匹配。例如，一个？将匹配“ an”，“ and”和“ a”。我有一堆字符串保存到向量中，并且正在使用for循环以允许通配符字符串与向量中的每个字符串竞争。我该如何编写一个递归函数来进行通配符匹配？

int searchFunction(string searchWord, vector<string> words);

bool wildCardFunction(string searchWord, string word);


bool wildCardMatch==(string *searchWord, string *word){
    if(*searchWord== '\0'&& *word == '\0')
        return true;

if (*searchWord == '?'|| *word==searchWord){
  return wilcardFunction(*searchWord+1, *word+1) ));
 }
 else{
  return false;
}

}

void searchWildcardFunction(string searchWord, vector<string> words){

for (unsigned i=0; i<words.size(); i++){
if(wildCardMatch(searchWord, words.at(i))==true){
  cout << "The word " << words.at(i) << "appears" << 
 searchFunction(words.at(i), words) << " times in this document." 
 <<endl;
  }
 }
 }

 bool containsWildcard(string searchWord){

for(int i=0; i<searchWord.length(); i++){
if(searchWord[i]='?'){
  return true;
}
return false;
 }

   }
 int searchFunction(string searchWord, vector<string> words){

int freq = 0;
for (unsigned i=0; i<words.size(); i++){
  if(words.at(i)==searchWord)
  freq++;
 }
 return freq;
}

Answer 1

正如评论中提到的那样，看起来您正在混合使用C样式字符串和C ++字符串。也不确定为什么需要递归函数。但是一种可能的解决方案是：

bool wildCardMatch(std::string const& searchWord, std::string const& word, size_t i) {
    auto const sSize = searchWord.size();
    auto const wordSize = word.size();
    if (sSize != wordSize) return false;
    if (sSize == i) return true;

    if (searchWord[i] == '?' || word[i] == searchWord[i]) {
        return wildCardMatch(searchWord, word, i + 1);
    }

    return false;
}

这是一个小测试，以确保它真正起作用：

bool test(std::string const& q, std::string const& word) {
    std::cout << "Testing (" << q << ", " << word << ")? ";
    return wildCardMatch(q, word, 0);
}


void expect_match(std::string const& q, std::string const& w) {
    if (test(q, w)) std::cout << "matched: SUCCESS\n";
    else std::cout << "no match: FAILED\n";
}


void expect_mismatch(std::string const& q, std::string const& w) {
    if (test(q, w)) std::cout << "matched: FAILED\n";
    else std::cout << "no match: SUCCESS\n";
}

int main(int argc, char** argv) {
    expect_match("", "");
    expect_match("?", "x");
    expect_match("a??", "abc");
    expect_match("a?c", "abc");
    expect_match("a??", "aaa");

    expect_mismatch("", "a");
    expect_mismatch("a", "");
    expect_mismatch("?", "");
    expect_mismatch("a??", "baa");
    expect_mismatch("a?b", "abx");
    expect_mismatch("?av", "avx");
    expect_mismatch("a??", "aasdsad");
    expect_mismatch("a??", "a");
    expect_mismatch("???", "da");
}