2

我正在开发一个程序来检查给定字符串中是否存在特定字符串：即一个字符串是否是另一个字符串的子字符串。

例如：

1)字符串：YoungPeople --> 要检查的子字符串：ungPeo

  The output should return true.

2）字符串：你好，你好吗？-->要检查的子字符串：l*are

    The output should return true.

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

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

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

我应该尝试使用相同的简单算法来搜索 * 之前的字符和之后的字符串吗？或者有没有更好的方法来解决这个问题？

4

4 回答 4

3

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

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

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

有更好的方法。接下来是递归的。

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

随着您遍历字符串，使用递归来检查字符串的其余部分。简单允许 2 个候选路径：
1 ) 推进 2) 推进 Else 匹配允许推进两者。 *
str
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;
  }

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

于 2013-06-09T15:38:03.893 回答
2

GNU Regex Library看起来就像您正在寻找的东西。如果您不熟悉正则表达式，请查看此站点。

于 2013-06-09T12:16:28.023 回答
1

这是你必须做的：

  1. 按 * 字符分割搜索字符串
  2. 在您正在搜索的字符串中查找每个部分（以正确的顺序）

或者，您可以按照其他人的建议使用正则表达式。

于 2013-06-09T15:41:56.807 回答
0

寻找良好编写的 glob 匹配实现的好地方是 bash 源。但这是一个有效的简单递归实现：

#include <assert.h>

int
_glob_match(char * pattern, char * str)
{
  if (!*pattern)          return 1;
  if (!*str)              return 0;
  if (*pattern == '*')    return match_any_tail(pattern + 1, str);
  if (*pattern != *str)   return 0;
  else                    return _glob_match(pattern + 1, str + 1);
}

int
match_any_tail(char * pattern, char * str)
{
  for (; *str; str++)
    if (_glob_match(pattern, str))
      return 1;
  return 0;
}

int glob_match(char * pattern, char * str)
{
  return match_any_tail (pattern, str);
}

void
main()
{
  assert(glob_match("ungPeo", "YoungPeople"));
  assert(glob_match("l*are",  "Hello How are You?"));
}
于 2013-06-09T18:58:31.497 回答