KMP算法的Java实现

灰太狼 2022-06-12 04:40 136阅读 0赞

### 输入 ###

第一行一个整数N，表示测试数据组数。

接下来的N\*2行，每两行表示一个测试数据。在每一个测试数据中，第一行为模式串，由不超过10^4个大写字母组成，第二行为原串，由不超过10^6个大写字母组成。

其中N<=20

### 输出 ###

对于每一个测试数据，按照它们在输入中出现的顺序输出一行Ans，表示模式串在原串中出现的次数。

import java.util.Scanner;
    
    public class Main{
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int N = Integer.parseInt(sc.nextLine());
    		String pattern = "", str = "";
    		for(int i = 0; i < N; i++){
    			pattern = sc.nextLine();
    			str = sc.nextLine();
    			System.out.println(KMP(pattern, str));
    		}
    	}
    
    	public static int KMP(String pattern, String str) {
    		int[] next = calNext(pattern);
    		int count = 0, i = 0, j = 0;//初始状态
    		while(i < str.length()){
    			if(str.charAt(i) == pattern.charAt(j)){//当前字符相同
    				if(j == pattern.length() - 1){//匹配成功
    					count++;
    					i++;
    					j = next[j];
    				}else{//继续匹配下一字符
    					i++;
    					j++;
    				}
    			}else{//当前字符不同
    				if(j == 0){//如果已经是模式串的第一个字符
    					i++;
    				}else{
    					j = next[j - 1];
    				}
    			}
    		}
    		return count;
    	}
    
    	/**
    	 * 计算next数组
    	 * @param pattern 模式串
    	 * @return
    	 */
    	public static int[] calNext(String pattern) {
    		int[] next = new int[pattern.length()];
    		next[0] = 0;
    		int i = 1, j = 0;
    		while(i < pattern.length()){
    			if(pattern.charAt(i) == pattern.charAt(j)){
    				next[i++] = ++j;
    			}else{
    				if(j == 0){
    					next[i++] = 0;
    				}else{
    					j = next[j-1];
    				}
    			}
    		}
    		return next;
    	}
    }