BF(Brute Force)算法为暴力匹配算法。其基本思路如下:
- 从
src的第一个字符开始和子串str的第一个字符进行比较，如果相等，则比较下一个，依次类推 - 如果不等，则从
src的第二个字符开始和子串str的第一个字符进行比较，如果相等，则比较下一个，依次类推 - 如果不等，则从
src的第三个字符开始比较.....
该算法比较简单，如果src长度为n，子串str长度为m，则时间复杂度为O(n*m):
/*
Brute Force算法，时间复杂度为O(m*n);
*/
char *BF(const char *src, const char *str) {
// 最终找到的位置的指针
char *ptr = NULL;
// src的遍历起始位置
const char *begin = src;
// 要查找的子串的长度
size_t length = strlen(str);
// 源串的长度
size_t src_length = strlen(src);
BEGIN:
while (1) {
// 子串比剩余src长，则直接返回
if (src_length - (begin - src) < length) {
break;
}
// 否则从src当前位置开始依次比较
for (int i = 0; i < length; i++) {
// begin不等于str
if (begin[i] != str[i]) {
// begin后移
begin++;
// 重新判断并循环
goto BEGIN;
}
}
// 如果一次for循环执行完毕，表示查找到了
ptr = (char *)begin;
break;
}
return ptr;
}
int main(int argc, const char * argv[]) {
__unused char *ptr = BF("hello world", "world");
return 0;
}
