import java.util.Scanner;
public class KMP算法 {
//计算目标串的前缀与后缀匹配关系
static void cal_next(String ptr1,int [] next){
char[] ptr = ptr1.toCharArray();//把字符串str1变成字符数组str
int plen = ptr1.length();
next[0] = -1;//-1表示不存在相同的最大前缀和最大后缀
int k = -1;//k初始化为-1,为什么是-1而不是0?
// 因为k其实要被用作kmp算法中的下标
//str[] = a b c a b d a b c a b c 在i=5时不匹配
//ptr[] = a b c a b c 在k=4时不匹配,因为匹配规则是ptr[k+1] == str[i]所以k=4
//这时目标串需要向后移动,移动3位,但是由于前缀abc与后缀abc相同,且后缀与主串已经比较过,
//所以移动三位后目标串前缀中的a b已经相当于已经与主串中的ab比较过,可以不用再次进行比较,这样就用到了next[]中k的值即下标
//k可以直接取到next[4]=1,k=1,进行ptr[k+1]==str[i]的最新比较,提高效率
for (int p = 1;p <= plen - 1;p ++){//对目标串自己进行比较
while(k > -1 && ptr[k+1] != ptr[p]){
k = next[k];//向前回溯
}
if(ptr[k+1] == ptr[p]){//相同,k++
k = k+1;
}
next[p] = k;//这个是把算的k的值(就是相同的最大前缀和最大后缀长)赋给next[p]
}
}
//KMP
static int KMP(String str1,String ptr1){
char[] str = str1.toCharArray();//把字符串str1变成字符数组str
char[] ptr = ptr1.toCharArray();//把字符串ptr1变成字符数组ptr
int slen = str1.length();
int plen = ptr1.length();
//创建一个next数组,数组长度为目标串长度plen
int [] next = new int [plen];
//计算next数组
cal_next(ptr1,next);
int k = -1;//k用来标识目标串下标
for(int i = 0;i < str1.length();i ++){
//k>-1表示有部分匹配,ptr[k+1] != str[i]表示在i下标位置不匹配
while(k > -1 && ptr[k+1] != str[i]){
k = next[k];//k赋值为next[k],目的是让k可以不用重复比较前缀与后缀相偶同的长度的字符
}
if(ptr[k+1] == str[i]){//匹配则向后移动
k++;
}
if(k == plen-1){//k移动到ptr的最末端
return i-plen+1;
}
}
return -1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入主串:");
String str1 = scanner.next();
System.out.println("请输入字串:");
String ptr1 = scanner.next();
// String str1 = "abcabdabcabc";
// String ptr1 = "abcabc";
System.out.println("主串:"+str1);
System.out.println("子串:"+ptr1);
int a = KMP(str1,ptr1);
if(a == -1){
System.out.println("不匹配");
}else{
System.out.println("从第"+a+"个位置后匹配");
}
}
}