我正在开发一个程序来检查给定字符串中是否存在特定字符串:也就是说,如果一个字符串是另一个字符串的子字符串。
例如:
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.
我使用了基于朴素的搜索算法,它对第一个输入非常有效。
但是我在第二种输入中遇到了问题,其中存在星号 (*),应该将其视为正则表达式:即匹配零个或多个字符。
我应该如何检查带有 * 符号的子字符串?
我是否应该尝试使用相同的朴素算法来搜索 * 之前的字符和之后的字符串?还是有更好的方法来解决这个问题?
最佳答案
我应该如何检查带有 * 符号的子字符串?
阅读 *
后,您需要尝试下面的 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;
}
[编辑之前版本的测试代码]
关于检查带星号 (*) 的字符串是否存在于另一个字符串中,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17009326/