Cod sursa(job #1742826)

Utilizator AplayLazar Laurentiu Aplay Data 17 august 2016 09:58:53
Problema Potrivirea sirurilor Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 1.88 kb
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class Main {

	public static int[] preprocess(String pattern) {
		int[] F = new int[pattern.length() + 1];

		for (int it = 2; it <= pattern.length(); ++it) {
			int j = F[it - 1];

			while (true) {
				if (pattern.charAt(it - 1) == pattern.charAt(j)) {
					F[it] = j + 1;
					break;
				}

				if (j == 0) {
					F[it] = 0;
					break;
				}

				j = F[j];
			}
		}

		return F;
	}

	public static int match(String string, String pattern, int[] F, List<Integer> results) {
		int answer = 0, stringIndex = 0, patternIndex = 0;

		while (true) {
			if (stringIndex == string.length()) {
				break;
			}

			if (string.charAt(stringIndex) == pattern.charAt(patternIndex)) {
				++stringIndex;
				++patternIndex;

				if (patternIndex == pattern.length()) {
					++answer;
					if (results.size() < 1000) {
						results.add(stringIndex - pattern.length());
					}
					patternIndex = F[patternIndex];
				}
			} else {
				if (patternIndex == 0) {
					++stringIndex;
				} else {
					patternIndex = F[patternIndex];
				}
			}
		}

		return answer;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new FileReader("strmatch.in"));
		BufferedWriter writer = new BufferedWriter(new FileWriter("strmatch.out"));

		String pattern = reader.readLine();
		String string = reader.readLine();

		int[] F = preprocess(pattern);
		List<Integer> results = new ArrayList<>();
		int matches = match(string, pattern, F, results);

		writer.write(matches + "\n");
		for (Integer startPosition : results) {
			writer.write(startPosition + " ");
		}

		reader.close();
		writer.close();
	}

}