//BF算法 枚举的思想 逻辑 BF O(n*m KMP O(nm)//1 申请俩个指针i和j 分别指向主串和子串的开始位置//2 进入while循环 循环的条件是i和j还合法//3 比较i和j指向的字符如果相同 则让i和j同步向后一个位置//4 如果不相同 则让指向子串的j变量 回退到开始位置 让指向主串的i变量也需要回退 回退到这一趟失败匹配的下一个字符//5 如果while循环进不去 则说明代码结束了 只需要对j进行判断#includestdio.h#includeassert.h#include stdlib.h#include string.h#include errno.hint BF_Search(const char* MainStr, const char* SubStr){assert(MainStr ! NULL SubStr ! NULL);int i 0;int j 0;int mainlen strlen(MainStr);int SubStrlen strlen(SubStr);while (i mainlen j SubStrlen){if (MainStr[i] SubStr[j]){i;j;}else{i i - j 1;j 0;}}if (j SubStrlen){return -1;}return i - j;}//KMP的核心 i打死不回退// 最长公共前后缀 再一个字符串里 找到俩个真子串 且一个顶头开始 另一个顶尾结束 且一模一样 长度还最长//场景一 当发生失配现象时 对应j指向的子串的位置 向前看可以找到最长公共前后缀、//总结 已知条件//1 当发生失配现象时 i已经走过的主串的路程 和j已经走过的子串的路程是一模一样的//2 从上红和下红中截取同一段路程 则也一定相同// 我们给的条件//1 当发生失配现象时 j指向的子串位置向前看 可以找到最长公共前后缀//推论 因为下蓝和右绿是同一个东西 可以有左绿上蓝//既然能证明存在左绿上蓝 则当发生失配现象时 i要么回退的位置没意义 则不用回退//当然如果i回退的位置的字符和j指向的子串0下标字符匹配成功 则回退有意义 但是i和j接下来要走的路径是左绿和上蓝 是100%成功的//则默认已经走过了//换句话说 i要么回退没意义 要么回退有意义 但是可以通过让j不用无脑回退到0 而是让j回退到一个合适的位置 从而把i回退到有意义位置抵消掉//场景二 当发生失配现象时 对应j指向的子串的位置 向前看不可以找到最长公共前后缀//总结 已知条件//1 当发生失配现象时 i已经走过的主串的路程 和j已经走过的子串的路程是一模一样的//2 从上红和下红中截取同一段路程 则也一定相同// 我们给的条件//1 当发生失配现象时 j指向的子串位置向前看 不可以找到最长公共前后缀//推论 因为下蓝和右绿是同一个东西 可以有左绿上蓝//因为下蓝和右绿是同一个东西 可以有左绿上蓝//场景2 i可以不用回退 要么i回退的位置没意义 要么i回退的位置有意义 但是因为不存在左绿上蓝 所有i回退之后一开始//好像比较成功 但是i接着向后走 再次走到原本失配的位置过程中 一定会有一个位置和j指向的字符匹配失败//因为j指向的子串可以在任何位置发生失配现象 则子串的任意一个位置都应该有一个合适的回退下标//则可以用一个数组来存储字串的全部回退位置信息 这个数组就是next数组// KMP算法应用// A B A B C A B C D A B C D E//-1 0 0 1 2 0 1 2 0 0 1 2 0 0// 0 1 1 2 3 1 2 3 1 1 2 3 1 1// A A A A A A A A A A B//-1 0 1 2 3 4 5 6 7 8 9// 0 1 2 3 4 5 6 7 8 9 10// A B C D A B C//-1 0 0 0 0 1 2// 0 1 1 1 1 2 3// A A B A A B A A//-1 0 0 0 1 2 3 1// 1 1 1 1 2 3 4 2// A B B B A B B B A C//-1 0 0 0 0 1 2 3 4 5// 0 1 1 1 1 2 3 4 5 6
