乐清网络,网站seo优化全程记录思维导图,做电商网站报价,长沙百度首页排名KMP算法总结 BF算法引导BF算法步骤#xff08;图片演示#xff09;代码演示 KMP算法推next数组代码演示 BF算法引导
BF算法是一个暴力的字符串匹配算法#xff0c;时间复杂度是o#xff08;m*n#xff09; 假设主串和子串分别为
我们想要找到子串在主串的位置 BF算法核… KMP算法总结 BF算法引导BF算法步骤图片演示代码演示 KMP算法推next数组代码演示 BF算法引导
BF算法是一个暴力的字符串匹配算法时间复杂度是om*n 假设主串和子串分别为
我们想要找到子串在主串的位置 BF算法核心BF算法就是同时遍历子串和主串如果不相同就将子串指针回退到首位主串指针回退到这次遍历的起点的下一个位置 我们指定主串的指针为i子串的指针为j如下图
BF算法步骤图片演示
匹配的过程我将用图来阐释 1.第一趟 i; j; i; j; 这时我们发现i和j指向的内容不一样了 这时我们进入下一趟 2.第二趟 ii-j1; (这里就是主串指针回退到这次遍历的起点的下一个位置因为每次都是i和j同时走但j每次都是从0开始走j同时记录了i每次走了多少步i-j就是回退到这一趟的起点但这个起点我们试过了就是1从下一个位置开始试) j0;
这里我们发现i和j指向的内容不一样了 这时我们进入下一趟 3.第三趟
ii-j1; j0; i; j; i; j; 这里我们发现i和j指向的内容不一样了 这时我们进入下一趟 4.第四趟 ii-j1; j0; 这里我们发现i和j指向的内容不一样了 这时我们进入下一趟 5.第五趟 ii-j1; j0; 这里我们发现i和j指向的内容不一样了 这时我们进入下一趟 6.第六趟 ii-j1; j0; i; j; i; j; i; j; i; j; 这时我们发现主串和子串都遍历结束这个例子有点奇怪一般只有一个遍历结束整个程序就能判断是否有子串并找到子串位置 我们不难发现只有当子串遍历完才能说明主串有这个子串
代码演示
public class BF {static int Bf(String S,String s){//空字符串if(Snull||snull){return -1;}//主串长度int SUMS.length();//子串长度int sums.length();//字符串长度为0if(SUM0||sum0){return -1;}//指针int i0;int j0;while (iSUMjsum){if(S.charAt(i)s.charAt(j)){i;j;}else {ii-j1;j0;}}if(jsum){return i-j;}return -1;}public static void main(String[] args) {System.out.println(Bf(aacascscc,ac));}
} KMP算法
KMP也是一种字符串匹配算法只不过他利用了遍历过的串的信息减少了趟数最重要就是理解他怎么利用信息 举个例子 我们指定主串的指针为i子串的指针为j如下图 i j; 一直到匹配不正确的地方
我们想让I指针停下来只移动j指针这是我们想的就是这时i要回退我们不想让他回退但又不能丢下前面的所以我们看前面还有什么能用上的这时我们遍历了主串的ABAB ,和子串的ABAB他们两个肯定是相同的因为刚刚遍历了如果不相同肯定会停下来如果是BF算法我们肯定会ii-j1;j;但现在我们想利用我们遍历过的ABAB的信息我的方法是向后拖拽子串只要发生拖拽主串的开头A和子串结尾的B肯定是用不上了我们必须求的是主串的从后面开始如果是从BAB开始算前缀即使前面匹配后面不匹配也没有用后缀和子串的从前面开始前缀这里就是为什么求主串的后缀和子串的前缀 拖拽两次我们发现主串和子串有AB重叠这时我们就能继续遍历了我的思考是这里我们利用了ABAB重叠的信息省去了i指针回退到主串的下标为2子串下标为0的地方一点点匹配而主串前面AB我们发现没有匹配所以就丢弃 现在我们想知道怎么利用匹配过的信息怎么一下就能找到拖拽后j到的位置 就要引入next数组来存储j指针在每个位置匹配失败要回退到哪
推next数组
假设有这样一个字符串 规则如下 前两个下标为01的就是固定的 从下标为2开始假设匹配失败了ab内找以a开头以b结尾除了本身没有这样的字符串回退到0 下标为3时假设匹配失败了aba内找以a开头以a结尾有这样的字符串回退到1 下标为3时假设匹配失败了abab内找以a开头以b结尾有这样的字符串回退到2 后面的自行计算结果为 给个例题请求出他的next数组 接下来我们进行一个推理 设原字符数组为p【】 如上图所示next【i】k假设p【i】p【k】如上图所示那么 p【0】…p【k-1】p【x】…p【i-1】 又已知k-0i-x得到xi-k p【0】…p【k-1】p【i-k】…p【i-1】 又因为p【i】p【k】所以p【0】…p【k】p【i-k】…p【i】 所以next【i1】k1 推出来的意思是p【8】这个前面有abc和前面的abc匹配p【3】和p【8】又相等那么p【9】找前面的匹配时直接p【8】前面找到的abc加p【8】 如上图所示next【i】k假设p【i】p【k】如上图所示那么 不是我们要找的我们就再回退到k0这时p【i】p【k】 这时我们又能用next【i1】k1next【6】k11
代码演示
public class KMP {public static void main(String[] args) {System.out.println(KMP(CSA,SA));}public static int KMP (String s, String sub){int lens s.length(), lensub sub.length();int[] next new int[lensub];//next数组 存放匹配不上的子串要跳跃的下标getNext(next, sub);int i 0, j 0;// i 遍历主串 j 遍历子串while (i lens j lensub) {if (j -1 || s.charAt(i) sub.charAt(j)) {i;j;//逐一比较相同的看下一个//当子串的第一个字符就与主串的字符不相等时j为0i向后移动一位} else {j next[j];}}if (j lensub) {return i - j;//上面while循环结束条件是因为 遍历发现子串所有均与主串相等} else {return -1;}}public static void getNext ( int[] next, String sub){next[0] -1;next[1] 0;//固定int i 2;//i表示当前所求next数组的下标int k 0;//比较是否相等的前一项while (i sub.length()) {if (k -1 || sub.charAt(i - 1) sub.charAt(k)) {//就是一直回退直到就是说没有利用的重叠部分就是k-1next[i] k 1;//当k-1时证明【0】与【j-1】里无相等字符k为0i移向下一位k;i;} else {k next[k];}}}}
之后如果有新的想法会及时补充大家如果有不同见解欢迎评论区留言
