手机app网站,dw网页设计心得体会,广告开户,网站关键词分析工具KMP算法#xff0c;字符串匹配算法#xff0c;给定一个主串S#xff0c;和一个字串T,返回字串T与之S匹配的数组下标。 在学KMP算法之前#xff0c;对于两个字符串#xff0c;主串S#xff0c;和字串T#xff0c;我们根据暴力匹配#xff0c;定义两个指针#xff0c;i指…KMP算法字符串匹配算法给定一个主串S和一个字串T,返回字串T与之S匹配的数组下标。 在学KMP算法之前对于两个字符串主串S和字串T我们根据暴力匹配定义两个指针i指向主串S的起始j指向字串T的起始依次比较如果主串i位置的值等于子串j位置的值ij。直到i位置的值和j位置的值不相同i回溯到起始位置1同时字串T的起始位置后移到i所在位置。直到匹配成功或者子串T后移长度T本身长度S主串的长度。这个暴力求解的复杂度因为有i的回溯需要2层循环i,j的移动因此时间复杂度为T(n*m,n是S的长度m是T的长度。 根据暴力匹配的思想我们接下来分析一下KMP算法。同样两个字符串按位比较而KMP算法的核心在于当主串的i位置的值和子串的j位置的值不同时主串Si前面的字符串与字串Tj前面的字符串已经匹配相等因为两者相等所以只需要拿出子串T前面的字符串根据T前面的字符串来计算一个next[j]数组将j回溯即可。问题便转换为求子串的next[j]数组。那么next[j]数组的求法为i前面的字符串分别取前缀和取后缀如果前缀的长度后缀的长度则j的值字符串缀长1存入next数组。否则j回溯给next[j]。直到j字串长度则next数组计算完成。后续根据i不回溯j从next数组里取值便可将字串T和主串S进行匹配直到字串T移出到主串S的长度匹配成功返回i下标匹配失败返回0。因为KMP算法简化了问题的求解将难点转换为求next数组并且i不回溯可以做到边移动边匹配。因此时间复杂度为T(nm) 下面是JAVA实现代码 public static void main(String[] args) {String S abababcabcabc;String T bcabc;int pos KMP(S,T);System.out.println(pos);}private static int KMP(String s, String t) {int i 0;//i指向Sint j 0;//j指向Twhile (is.length()jt.length()){if(j-1||s.charAt(i)t.charAt(j)){//为什么j-1,i和j也需要后移当j-1,说明字串和主串的起始点在0,i;//i后移j;//j后移}else{j getNext(t)[j]; //j根据t求一个next数组next数组的作用就是j根据内部的值回溯。}}if(j t.length()){ //j已经等于t的长度了说明匹配结束了。return i-t.length(); //字串起始点就是i-j或者i-t.length()}else{return -1;//匹配失败了。}}private static int[] getNext(String t) {int i 0;//next数组下标,初始值0int j -1;//j指向字符串t,初始值-1int [] next new int[t.length()];//构造next数组长度为t的长度。next[0] -1;//next数组从1开始存值即0号位置存默认值-1;while (it.length()-1){if(j-1||t.charAt(i)t.charAt(j)){//j-1表示从头开始遍历t,或者t的前缀t的后缀都要将j1存入next数组i;j;next[i] j; //如果后缀前缀,将j1即j的值存入next数组。}else {j next[j]; //如果后缀前缀j回溯到next[j]位置}}return next;}
输出结果 5 完全正确。
