广州建设工程质量安全网站,网页设计代码大全html,管理培训班,建网站收费多少钱KMP算法详解 1 KMP算法解决的问题 2 前缀问题 3 KMP 算法 1 KMP算法解决的问题
字符串str1和str2#xff0c;str1是否包含str2#xff0c;如果包含返回str2在str1中开始的位置。并做到时间复杂度为 O ( n ) O(n) O(n) 2 前缀问题
求一个字符串中每个字符前缀和后缀相… KMP算法详解 1 KMP算法解决的问题 2 前缀问题 3 KMP 算法 1 KMP算法解决的问题
字符串str1和str2str1是否包含str2如果包含返回str2在str1中开始的位置。并做到时间复杂度为 O ( n ) O(n) O(n) 2 前缀问题
求一个字符串中每个字符前缀和后缀相等的最大长度 比如求字符串 : a b b a a b b a b b a a b b a k l
假设此时来到的位置为 i
求解方法如下: 先看i - 1 位置的 前缀和后缀相等的最大长度 CN ;
比较 CN 位置和 i - 1位置的字符串是否相等,如果相等,则i位置的前缀和后缀相等的最大长度为 CN 1;
如果不相等,得到 CN位置的前缀和后缀相等的最大长度CN,继续用CN位置的字符和 i - 1位置的字符比较
循环上述过程,碰到CN为0,则i位置的 前缀和后缀相等的最大长度为0
比如求字符串 a b b a a b b a b b a a b b c k l k字符的前缀和后缀相等的最大长度过程如下 : k所在的位置 15,前一个位置的字符为 c 字符c 前缀和后缀相等的最大长度cn 为7, 则比较字符串中 7 位置 a和 15 -1 位置的字符 a 相等,则直接返回 8
获取一个字符串中所有字符前缀和后缀相等的最大长度代码实现
coding
/**** param m 获取字符数组m每一个位置 前缀和后缀相等的最大长度* return*/public static int[] getNextArr(char[] m){if (m.length 1){return new int[]{-1};}int[] retArr new int[m.length];// 规定 0 位置 前缀和后缀相等的最大长度为 -1// 规定 1 位置 前缀和后缀相等的最大长度为 0retArr[0] -1;retArr[1] 0;// 使用字符数组中那个位置的字符与 i - 1 位置的字符进行比较int cmpIndex 0; // i - 1位置的字符前缀和后缀相等的最大长度// i在2位置时,使用i - 1位置的,即 1位置的字符前缀和后缀相等的最大长度// 初始时,使用 0 位置的字符和1位置的字符比较int i 2;while (i m.length){// cmpIndex位置字符和i位置的字符相等 // 则i位置的前缀和后缀相等的最大长度为cmpIndex1if (m[cmpIndex] m[i - 1]){retArr[i] cmpIndex;} else if (cmpIndex 0){cmpIndex retArr[cmpIndex];} else {retArr[i] 0;}}return retArr;}3 KMP 算法
coding
/*** KMP算法解决的问题* 字符串str1和str2str1是否包含str2如果包含返回str2在str1中开始的位置。* 如何做到时间复杂度O(N)完成* 字符串1的长度是M* 字符串的长度是N* 暴力匹配的时间复杂度O(M * N)* 前缀和后缀相等的最大长度* 前缀和后缀不能取到整体**/public static int getIndex(String s1,String s2){if (s1 null || s2 null || s2.length() 1 || s2.length() s1.length()){return -1;}char[] str1 s1.toCharArray();char[] str2 s2.toCharArray();int[] nextArr getNextArr(str2);int i1 0;int i2 0;while (i1 str1.length i2 str2.length){if (str1[i1] str2[i2]){i1;i2;} else if (nextArr[i2] -1){//第一个字符i1 ;} else {// i2直接到 i2位置前缀和后缀相等最大长度的位置i2 nextArr[i2];}}// 只有 i1 str2.length时才匹配成功 否则str2就不在str1中return i2 str2.length ? i1 - i2 : -1;}
