欢迎大家来到IT世界,在知识的湖畔探索吧!
“`
package DataStructure;
public class KMP {
public int indexOf(String source, String pattern) {
int i = 0, j = 0;
char[] src = source.toCharArray();
char[] ptn = pattern.toCharArray();
int sLen = src.length;
int pLen = ptn.length;
int[] next = getNext(ptn);
while (i < sLen && j < pLen) {
// 如果j = -1,或者当前字符匹配成功(src[i] = ptn[j]),都让i++,j++
if (j == -1 || src[i] == ptn[j]) {
i++;
j++;
} else {
// 如果j!=-1且当前字符匹配失败,则令i不变,j=next[j],即让pattern模式串右移j-next[j]个单位
j = next[j];
}
}
if(j == pLen) {
return i – j;
}
return -1;
}
public int[] getNext(char[] p) {
// 已知next[j] = k,利用递归的思想求出next[j+1]的值
// 如果已知next[j] = k,如何求出next[j+1]呢?具体算法如下:
// 1. 如果p[j] = p[k], 则next[j+1] = next[k] + 1;
// 2. 如果p[j] != p[k], 则令k=next[k],如果此时p[j]==p[k],则next[j+1]=k+1,
// 如果不相等,则继续递归前缀索引,令 k=next[k],继续判断,直至k=-1(即k=next[0])或者p[j]=p[k]为止
int pLen = p.length;
int[] next = new int[pLen];
int k = -1;
int j = 0;
next[0] = -1; // next数组中第一位next[0]为-1
while (j < pLen – 1) {
if (k == -1 || p[j] == p[k]) {
k++;
j++;
next[j] = k;
} else {
k = next[k];
}
}
return next;
}
public static void main(String[] args){
KMP kmp = new KMP();
String a = “ababc”;
String b = “ababababcababc”;
int[] next = kmp.getNext(a.toCharArray());
for(int i = 0; i < next.length; i++){
System.out.println(a.charAt(i)+” “+next[i]);
}
int res = kmp.indexOf(b, a);
System.out.println(res);
}
}
“`
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://itzsg.com/38505.html
