package shujujiegou;
/** * Created by lcc on 2017/7/6. */ public class Kmp {
public static void main(String[] args) { String str1 = "aabaaacabcaaabaaabcabab"; String str2 = "abcabab"; int[] next = getNext(str2); int[] next1 = getNext1(str2); for (int i = 0; i < next.length; i++) { System.out.println(next[i] + " " + next1[i]); } System.out.println("--------------------------"); int index = KmpIndex(str1, str2); System.out.println(index); String str3 =str1.substring(16); System.out.println(str3); } static int KmpIndex(String str1, String str2) { char[] p1 = str1.toCharArray(); char[] p2 = str2.toCharArray(); int[] getNext = getNext(str2); int j = 0; int i = 0; while (i < str1.length() && j < str2.length()) { if (j == -1 || p1[i] == p2[j]) { i++; j++; if (j == str2.length()) { return i-j; } } else { j = getNext[j]; } } return -1; } static int[] getNext(String str) { int[] next = new int[str.length()]; char[] p = str.toCharArray(); int j, k; next[0] = -1; j = 0; k = -1; while (j < str.length() - 1) { if (k == -1 || p[j] == p[k]) //匹配的情况下,p[j]==p[k] { j++; k++; next[j] = k; } else //p[j]!=p[k] k = next[k]; } return next; } static int[] getNext1(String str) { int[] next = new int[str.length()]; char[] p = str.toCharArray(); for (int i = 0; i <= str.length() - 1; i++) { if (i == 0) { next[0] = -1; continue; } if (i == 1) { next[1] = 0; continue; } int z = 0; int aa = 0; int maxcount = 0; for (int j = 1; j < i; j++) { if (p[j] == p[z]) { z++; maxcount++; } else { j = j - maxcount; maxcount = 0; z = 0; aa = 0; } aa = maxcount - aa > 0 ? maxcount : aa; } next[i] = aa; } return next; }}
