KMP字符串模式匹配算法实(Java代码)

解题思路: 写一个kmp算法的方法 多调用几遍方法就好了

参考代码:

import java.util.Scanner;

public class KMP字符串模式匹配算法实现 {

	public static void main(String[] args) {
		// 3组字符串，每组字符串占一行。每行包含由空格分隔的两个字符串，字符串仅由英文小写字母组成且长度不大于100。
		// 每组数据输出1行，输出后一个字符串在前一个字符串中的位置，如果不匹配，则输出0。
		
		Scanner sc = new Scanner(System.in);
		String[][] arr = new String[3][2];
		
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[i].length; j++) {
				arr[i][j] = sc.next();
			}
		}
		
		int[] next1 = kmpNext(arr[0][1]);
		int[] next2 = kmpNext(arr[1][1]);
		int[] next3 = kmpNext(arr[2][1]);
		
		System.out.println(kmpSeek(arr[0][0], arr[0][1], next1) +1); //加1是因为下标是从0开始的并且返回的是-1
		System.out.println(kmpSeek(arr[1][0], arr[1][1], next2) +1);
		System.out.println(kmpSeek(arr[2][0], arr[2][1], next2) +1);
		
	}
	
	// 查找匹配字符串
	public static int kmpSeek(String str1,String str2,int[] next) {
		for (int i = 0,j = 0; i < str1.length(); i++) {
			
			while(j > 0 && str1.charAt(i) != str2.charAt(j)) {
				j = next[j-1];
			}
			
			if(str1.charAt(i) == str2.charAt(j)) {
				j++;
			}
			
			if(j == str2.length()) {
				return i - j + 1;
			}
		}
		return -1;
	}
	
	// 获取str2的部分匹配值
	public static int[] kmpNext(String str2) {
		// 创建一个数组保存部分匹配值
		int[] next = new int[str2.length()];
		next[0] = 0;
		
		for (int i = 1,j = 0; i < str2.length(); i++) {
			
			while(j > 0 && str2.charAt(i) != str2.charAt(j)) {
				j = next[j-1];
			}
			
			if(str2.charAt(i) == str2.charAt(j)) { // 满足时部分匹配值加1
				j++;
			}
			next[i] = j;
		}
		return next;
	}
	
}