POJ3461-Oulipo

Main.java

import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

	static Scanner cin = new Scanner(System.in);
	static PrintWriter cout = new PrintWriter(System.out, true);

	int MAXV = 10012;

	int[] next = new int[MAXV];

	private void buildNextArray(String pattern) {
		next[0] = -1;
		for (int i = 0, j = -1; pattern.length() > i;) {
			if (j == -1 || pattern.charAt(j) == pattern.charAt(i)) {
				i++;
				j++;
				next[i] = j;
			} else
				j = next[j];
		}
	}

	private int KMP(String pattern, String text) {

		buildNextArray(pattern);

		int cnt = 0;
		for (int i = 0, j = 0; text.length() > i;) {
			if (j == -1
					|| (j < pattern.length() && pattern.charAt(j) == text
							.charAt(i))) {
				i++;
				j++;
				if (j == pattern.length())
					cnt++;
			} else
				j = next[j];
		}
		return cnt;
	}

	public void solve() {
		cout.println(KMP(cin.nextLine(), cin.nextLine()));
	}

	public static void main(String[] args) {
		Main main = new Main();

		int times = cin.nextInt();
		cin.nextLine();
		while (times-- > 0)
			main.solve();
	}

}

赞！b(￣▽￣)d。。虽然不会JAVA~