django网站开发,网站设计ps做效果图过程,山西推广公司,做网站需要提供什么串的模式匹配#xff1a;在主串str的pos位置查找子串sub#xff0c;找到返回下标#xff0c;没有找到返回-1。
1.BF算法思想
相等则继续比较#xff0c;不相等则回退#xff1b;回退是i退到刚才位置的下一个#xff08;i-j1#xff09;;j退到0#xff1b;利用子串是否…串的模式匹配在主串str的pos位置查找子串sub找到返回下标没有找到返回-1。
1.BF算法思想
相等则继续比较不相等则回退回退是i退到刚才位置的下一个i-j1;j退到0利用子串是否遍历完成来判断是否查找成功注意不能利用主串来判断 2.代码实现
int BF(const char* str, const char* sub, int pos)
{assert(str ! NULL sub ! NULL);if (strNULL||subNULL||pos0 || posstrlen(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 lenstrj lensub){if (str[i] sub[j]){i;j;}else{i i - j 1;//刚才位置的下一个j 0;}}//判断是否查找成功利用子串是否遍历完成来判断是否查找成功//if (sub[j] \0)if(jlensub)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)
