wordpress 图片无法显示,seo网络推广公司排名,wordpress优酷视频,杭州软件制作KMP算法Java实现
KMP算法简介 KMP算法是一种高效的字符串匹配算法#xff0c;核心是利用匹配失败后的信息#xff0c;尽量减少模式串与主串的匹配次数已达到快速匹配的目的。通过一个next()函数实现#xff0c;该函数包含了模式串的局部匹配信息#xff0c;KMP算法的时间复…KMP算法Java实现
KMP算法简介 KMP算法是一种高效的字符串匹配算法核心是利用匹配失败后的信息尽量减少模式串与主串的匹配次数已达到快速匹配的目的。通过一个next()函数实现该函数包含了模式串的局部匹配信息KMP算法的时间复杂度是O(mn)。 算法步骤
寻找最大前缀后缀公共子串长度 对于P p0 p1 …pj-1 pj寻找模式串P中长度最大且相等的前缀和后缀。如果存在p0 p1 …pk-1 pk pj-k pj-k1…pj-1 pj那么在包含pj的模式串中有最大长度为k1的相同前缀后缀。 1以模式串ABAB为例子串ABA有长度为1的相同前缀后缀A子串ABAB有长度为2的相同前缀后缀AB相同前缀后缀长度k1为2)。
模式串ABAB最大前缀后缀公共子串长度0012
求next数组 next数组是除了当前字符外的最长相同前缀后缀通过第一步得到最大长度后将整体右移一位然后初值赋值为-1。 模式串ABABnext数组-1001
根据next数组进行匹配 匹配失败j next[j]模式串向右移动的位数为j - next[j]。也就是说模式串的后缀pj-k pj-k1, …, pj-1 跟文本串si-k si-k1, …, si-1匹配成功但pj 跟si匹配失败时因为next[j] k相当于在不包含pj的模式串中有最大长度为k 的相同前缀后缀即p0 p1 …pk-1 pj-k pj-k1…pj-1故令j next[j]从而让模式串右移j - next[j] 位使得模式串的前缀p0 p1 …pk-1 对应着文本串si-k si-k1, …, si-1而后让pk 跟si 继续匹配。 算法实例
public class KMP {public static void main(String[] args) {String str1 BBC ABCDAB ABCDABCDABDE;String str2 ABCDABD;//使用模式串获得next数组int[] next getNext(str2);int index kmp(str1, str2, next);System.out.println(index);}private static int kmp(String source, String pattern, int[] next) {char[] s source.toCharArray();char[] p pattern.toCharArray();int sLen s.length;int pLen p.length;for (int i0,j0;isLen;i) {while(j0 s[i] ! p[j]) {j next[j-1];}if (s[i] p[j]) {j;}if (j pLen) {return i-j;}}return -1;}//获取模式串的部分匹配表private static int[] getNext(String dest) {char[] p dest.toCharArray();int pLen p.length;int[] next new int[pLen];for (int i0;ipLen;i) {while(j0 p[i] ! p[j]) {j next[j-1];}if (p[i] p[j]) {j;}next[i] j;}return next;}/*** 获得next数组* param next next数组* param t 模式串* return int[] 返回数组*/private static void getNext(int[] next, String t){//对于模式串中每个元素tj都存在一个实数k//使得模式串t开头的k个字符t0t1...tk-1依次与tj前面的k个字符相同//如果这样的k有多个则取最大的一个int j 0, k -1;next[0] -1;char[] p t.toCharArray();int len p.length;while(j len){if(k -1 || p[j] p[k]){j;k;next[j] k; //如果p[j]与p[k]相同了最大前后缀长度加1}else{k next[k];}}}
}
