比较字符串与通配符

Question

在 C 中，我如何准确地将包含 *(可以是字符的任意组合)的字符串与字符串的二维矩阵进行比较？

例如，我有单词go*s。它可以生成单词“gorgeous”(* 是“orgeou”)、“goodness”、“goats”、“goes”等。我应该从整本词典中读取单词并进行比较包含一个或多个星号的单词 (*)。每个可以从带有星号的单词生成的单词都必须被打印出来。如果两个单词的长度相同，那么很容易比较，因为*只能是一个字母。

int fq(char *s1, char *s2){
int i, a=0, b=0, s=0;
while (1){
    if (s1[a]=='\0')
        break;
    a++;
}
if (strlen(s1)==strlen(s2)){
    for(i=0; i<a; i++){
        if (s1[i]=='*'){
            b++;
            }
        if (s1[i]==s2[i]){
            b++;
            }
        }
    }
if (b==a)
    return 1;

Answer 1

通过逐个字符地检查模式字符串并应用这些规则，您可以很容易地编写一个递归函数来比较字符串与另一个带有通配符的字符串:

• if pattern[p] == '\0': 如果 candidate[c] == '\0' 模式匹配
• if pattern[p] == '*': 尝试将 candidate[c]...candidate[c+n] 与 pattern[p+1] 匹配
• 如果模式[p] != '?' and pattern[p] != candidate[c]: 不匹配
• 否则，将模式[p+1]与候选[c+1]匹配

这几条规则很容易写成匹配的递归函数:

#include <stdbool.h>

bool match(const char *pattern, const char *candidate, int p, int c) {
  if (pattern[p] == '\0') {
    return candidate[c] == '\0';
  } else if (pattern[p] == '*') {
    for (; candidate[c] != '\0'; c++) {
      if (match(pattern, candidate, p+1, c))
        return true;
    }
    return match(pattern, candidate, p+1, c);
  } else if (pattern[p] != '?' && pattern[p] != candidate[c]) {
    return false;
  }  else {
    return match(pattern, candidate, p+1, c+1);
  }
}

然后，您可以:

match("f*o", "foo", 0, 0);

这不是一个有效的方法，但我认为它很容易理解和实现。如果你需要更高效的东西，你可以从这些开始:http://en.wikipedia.org/wiki/String_searching_algorithm