mtjmtj7的小站
mtjmtj7的小站
© mtjmtj7
All Rights Reserved.

JAVA-KMP


public class kmp { public static int[] getNext(char[] p) { int[] next = new int[p.length]; next[0] = -1; int j = 0; int i = 1; while(i < p.length-1) { if(j == -1 || p[i] == p[j]) { ++i; ++j; next[i] = j; } else { j = next[j]; } } return next; } public static int kmp(char str[], char p[], int next[]) { int i = 0, j = 0; int n = str.length; int m = p.length; for (i = 0; i < n; i++) { while(j > -1 && str[i] != p[j]) { j = next[j]; } if(j == -1 || str[i] == p[j]) { j++; } if(j == m) { return i-j+1; } } return -1; } public static void main(String[] args) { String str = "abaabcaabcccabcc"; String p = "abc"; System.out.println(kmp(str.toCharArray(),p.toCharArray(),getNext(p.toCharArray()))); } }
打赏
2019-03-10
10 阅读
暂无评论

发表评论