Skip to content

Instantly share code, notes, and snippets.

@zhanggang807
Created March 9, 2018 01:36
Show Gist options
  • Save zhanggang807/4be777e616e82008e78d30078f45febd to your computer and use it in GitHub Desktop.
Save zhanggang807/4be777e616e82008e78d30078f45febd to your computer and use it in GitHub Desktop.
KMP算法
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class KMP {
public static void main(String[] args) {
//Scanner sc = new Scanner(System.in);
//String str1 = sc.nextLine();//主串
String str1 = "ababbabababbbab";//主串
//while (sc.hasNext()) {
// String str2 = sc.nextLine();//模式串
String str2 = "abababbbab";//模式串
int next[] = new int[str2.length()];
getNext(next, str2);//求解next数组
System.out.println("next数组" + java.util.Arrays.toString(next));
List<Integer> pos = new ArrayList<Integer>();//可能存在多个位置起始的字符串与模式串匹配,记录这些在主串中的位置
ifMatch(str1, str2, next, pos);//字符串匹配过程
System.out.println("匹配位置:" + pos);//输出所有匹配的位置
//}
}
private static void ifMatch(String str1, String str2, int[] next, List<Integer> pos) {
int j = 0;//主串初始位置
int s = 0;//匹配串初始位置
while (j < str1.length()) {
if (s == -1 || str1.charAt(j) == str2.charAt(s)) {//比较字符是否相等
j++;
s++;
if (s >= str2.length()) {//模式串被完全匹配
pos.add(j - str2.length());
s = 0;
j--;
}
} else {
s = next[s];//不等,主串j不变,模式串s变
}
}
}
//next数组的求解
private static void getNext(int[] next, String str) {
next[0] = -1;
int k = -1;
int j = 0;
while (j < str.length() - 1) {
if(k >=0){
System.out.println("k = " + k + " char-k = " + str.charAt(k) + " , j = " + j + " char-j = " + str.charAt(j));
} else {
System.out.println("k = " + k + " char-k不取值 , j = " + j + " char-j = " + str.charAt(j));
}
if (k == -1 || str.charAt(j) == str.charAt(k)) {//k==-1只为初始next数组的第二个元素为0
j++;
k++;
System.out.println("j = " + j + " , k = " + k);
next[j] = k;
System.out.println("next[" + j + "] = " + k + " ,,, next = " + printArr(next));
System.out.println("\n");
} else {
System.out.println("k = " + k);
System.out.println("next[" + k + "]====" + next[k]);
k = next[k];//不相等k又变成-1,所以j指定位的next数组值为0(上面k++了)
System.out.println("k = next[k] = " + k);
System.out.println("next = " + printArr(next));
System.out.println("\n");
}
//System.out.println("next = " + printArr(next));
}
// 0 1 2 3 4 5 6 7 8 9
// a b a b a b b b a b
}
private static String printArr(int[] arr){
StringBuffer sb = new StringBuffer("[");
for (int i : arr) {
sb.append(i).append(" ,");
}
sb.deleteCharAt(sb.length() - 1);
sb.append("]");
return sb.toString();
}
/**
* 你要求解当前位的next值,则看前一位与前一位next所在位字符是否相等,
* 相等则当前位的next等于前一位next+1,如果不等就找前一位next的next与前一位比较,
* 如果相等,当前位的next等于那个与前一位字符相等的字符所在位置+1,如果还是不相等,
* 则以此类推,直到出现比较位为next[]=-1,那当前位的next就等于-1
*/
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment