KMP

KMP

import java.util.*;

public class KMP {

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		//s是长文本，p是模式串，n是s的长度，m是p的长度，
		String s = sc.next();
		String p = sc.next();
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] ne = new int[10010];

		//求模式串的next数组
		for (int i = 2, j = 0; i < m; i++) {
			while (j != 0 && p.charAt(i) != p.charAt(j + 1))
				j = ne[j];
			if (p.charAt(i) == p.charAt(j + 1))
				j++;
			ne[i] = j;
		}

		//匹配
		for (int i = 1, j = 0; i <= n; i++) {
			while (j != 0 && s.charAt(i) != p.charAt(j + 1))
				j = ne[j];
			if (j == m) {
				j = ne[j];
			}
		}

	}
}