admin 管理员组

文章数量: 1086866

KMP实现

参考链接：
.html 图解
.html 代码

KMP要解决的问题是字符串匹配

输入：一个文本串S，和一个模式串P
输出：若干行，每行包含一个整数，表示s2在s1中出现的位置

详细原理参考上述链接，我自己对着写了一套代码

public static void main(String[] args) {KMP kmp = new KMP();String s = "ABACDABABC";int[] next = kmp.getNext(s);for(int i : next){System.out.print(i+" ");}String p = "ACD";System.out.println(kmp.find(s,p));
}
//next 数组获取
public int[] getNext(String s){int len = s.length();int[] next = new int[len];next[0] = -1;int k = -1;int j = 1;while(j<len-1){if(k==-1 || s.charAt(j)==s.charAt(k)){//匹配时，向后推进next[++j] = ++k;} else{//不匹配时，当前已经匹配的字符串子匹配，递归k = next[k];}}return next;
}
//字符串查找的具体实现
public int find(String str,String p){int len1 = str.length();int len2 = p.length();int[] next = getNext(p);int i=0,j=0;while(i<len1 && j<len2){if(j==-1 || str.charAt(i) == p.charAt(j)){++i;++j;} else{j = next[j];}}if(j==len2){return i-j;} else{return -1;}
}

本文标签： KMP实现

版权声明：本文标题：KMP实现 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1693718590a238764.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。