检查带星号 (*) 的字符串是否存在于另一个字符串中

Question

我正在开发一个程序来检查给定字符串中是否存在特定字符串:也就是说，如果一个字符串是另一个字符串的子字符串。

例如:

1)String: YoungPeople --> Substring to be checked: ungPeo

  The output should return true.

2)String: Hello How are You? --> Substring to be checked: l*are

    The output should return true.

我使用了基于朴素的搜索算法，它对第一个输入非常有效。

但是我在第二种输入中遇到了问题，其中存在星号 (*)，应该将其视为正则表达式:即匹配零个或多个字符。

我应该如何检查带有 * 符号的子字符串？

我是否应该尝试使用相同的朴素算法来搜索 * 之前的字符和之后的字符串？还是有更好的方法来解决这个问题？

Answer 1

我应该如何检查带有 * 符号的子字符串？

阅读 * 后，您需要尝试下面的 1-2。

...使用相同的朴素算法进行搜索...是否有更好的方法...？*

有更好的方法。一个递归紧随其后。

[编辑说明:6/10 发现/修复错误]

随着您对字符串的处理，使用递归检查字符串的其余部分。
* 简单允许 2 个候选路径:
1) 推进 str
2) 推进 substr
否则，匹配的 char 允许同时推进两者。

// StarCompare() helper function
bool StarCmp(const char *str, const char *pat) {
  if (*pat == '\0') return 1;
  if (*pat == '*') {
    if (*str) {
      // advance str and use the * again
      if (StarCmp(str + 1, pat)) return 1;
    }
    // let * match nothing and advacne to the next pattern
    return StarCmp(str, pat + 1);
  }
  if (*pat == *str) {
    return StarCmp(str + 1, pat + 1);
    }
  return 0;
}  

bool StarCompare(const char *str, const char *pat) {
  if (!str || !pat) return 0;
  do {
    if (StarCmp(str, pat)) return 1;
  } while (*str++);
  return 0;
  }

---

[编辑之前版本的测试代码]