package com.trs.utils;public class KMPStr {/** 在KMP算法中，最難求的就是next函數，如何理解next函數是一個難題，特別是k=next[k]，這里* 需要指出的是當p[i]!=p[j]時，我們只有通過回溯將k的值逐漸減小，貌似類似與用到了動態規劃的思想 參考網上阮一峰老師的博客講解的十分詳細*/private static int[] getNext(String t) {int[] next = new int[t.length()];next[0] = -1;int j = 0;int k = -1;while (j < t.length() - 1) {if (k == -1 || t.charAt(j) == t.charAt(k)) {j++;k++;next[j] = k;} else {k = next[k];}}for (int i : next) {System.out.print(i + ":");}System.out.println();return next;}public static int kmpStrIndex(String s, String t, int[] next) {int i = 0;int j = 0;while (i < s.length() && j < t.length()) {if (j == -1 || s.charAt(i) == t.charAt(j)) {i++;j++;} else {// i不變，j后退j = next[j];}if (j == t.length()) {return i - j;}}return -1;}}
?
