# 【数据结构与算法】字符串匹配KMP算法

benbmw2008 分享于 2014-09-03

//匹配字符串模式值  void getFail(char P[],int f[]) { int m=strlen(P); f[0]=0; f[1]=0; for(int i=1;i<m;i++) { int j=f[i]; while(j&&P[i]!=P[j])  j=f[j];

• 代码实现

```/**
* 源码名称：KMP.java
* 日期：2014-09-03
* 程序功能：KMP算法
* 作者：A2BGeek
*/
public class KMP {
public int[] getNext(String in) {
int[] next = new int[in.length()];
int j = 0;
int k = -1;
next[j] = k;
while (j < next.length - 1) {
if (k == -1 || in.charAt(k) == in.charAt(j)) {
j++;
k++;
next[j] = k;
} else {
k = next[k];
}
}
for(int i : next) {
System.out.print(i + " ");
}
System.out.println();
return next;
}

public int kmp(String s, String p) {
int i = 0;
int j = 0;
int[] next = getNext(p);
while (i < s.length() && j < p.length()) {
if (j == -1 || s.charAt(i) == p.charAt(j)) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == p.length()) {
return 1;
} else {
return -1;
}
}

public static void main(String[] args) {
KMP kmp = new KMP();
String s = "acbfdfjkdhg";
String p = "dfdj";
System.out.println(kmp.kmp(s, p));
}
}
```

×
• 登录
• 注册

×