串的匹配算法——BF算法（朴素查找算法）

串的模式匹配：在主串str的pos位置查找子串sub，找到返回下标，没有找到返回-1。

1.BF算法思想

相等则继续比较，不相等则回退；回退是i退到刚才位置的下一个（i-j+1）;j退到0；利用子串是否遍历完成，来判断是否查找成功；（注意：不能利用主串来判断）

2.代码实现

int BF(const char* str, const char* sub, int pos)
{assert(str != NULL && sub != NULL);if (str==NULL||sub==NULL||pos<0 || pos>strlen(str))return -1;int i = pos;int j = 0;int lenstr = strlen(str);int lensub = strlen(sub);//while (str[i] != '\0' && sub[j] != '\0')while(i < lenstr&&j < lensub){if (str[i] == sub[j]){i++;j++;}else{i = i - j + 1;//刚才位置的下一个j = 0;}}//判断是否查找成功，利用子串是否遍历完成，来判断是否查找成功//if (sub[j] == '\0')if(j>=lensub)return i - j;elsereturn -1;
}	int main()
{const char* str1 = "ababcabcdabcde";const char* str2 = "abcd";printf("%d\n", BF(str1, str2, 0));printf("%d\n", BF(str1, str2, 6));const char* str3 = "aaaaab";const char* str4 = "aaaab";printf("%d\n", BF(str3, str4, 0));printf("%d\n", BF(str3, str4, -1));printf("%d\n", BF(str3, str4,8));const char* str5 = "abcd";const char* str6 = "ae";printf("%d\n", BF(str5, str6, 0));return 0;
}

注：此算法时间复杂度为O(n*m)