Cod sursa(job #1743625)

Utilizator AplayLazar Laurentiu Aplay Data 18 august 2016 14:48:01
Problema Potrivirea sirurilor Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 2.29 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 {

	private static long SYMBOLS = 52;
	private static long MODULO1 = 1999999973;
	private static long MODULO2 = 1999999943;

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

		char[] pattern = reader.readLine().toCharArray();
		char[] string = reader.readLine().toCharArray();

		if (pattern.length > string.length) {
			writer.write("0");
		} else {
			long matches = 0, patternHash1 = 0, patternHash2 = 0, stringHash1 = 0, stringHash2 = 0, symbolsPower1 = 1,
					symbolsPower2 = 1;
			List<Integer> matchesStart = new ArrayList<>();

			for (int it = pattern.length - 1; it >= 0; --it) {
				patternHash1 = (patternHash1 + symbolsPower1 * pattern[it] % MODULO1) % MODULO1;
				patternHash2 = (patternHash2 + symbolsPower2 * pattern[it] % MODULO2) % MODULO2;
				stringHash1 = (stringHash1 + symbolsPower1 * string[it] % MODULO1) % MODULO1;
				stringHash2 = (stringHash2 + symbolsPower2 * string[it] % MODULO2) % MODULO2;
				
				if (it != 0) {
					symbolsPower1 = (symbolsPower1 * SYMBOLS) % MODULO1;
					symbolsPower2 = (symbolsPower2 * SYMBOLS) % MODULO2;
				}
			}

			if (patternHash1 == stringHash1 && patternHash2 == stringHash2) {
				++matches;
				matchesStart.add(0);
			}

			for (int it = pattern.length; it < string.length; ++it) {
				int prevStartIndex = it - pattern.length;

				stringHash1 = (SYMBOLS * (stringHash1 - (symbolsPower1 * string[prevStartIndex] % MODULO1) + MODULO1) + string[it]) % MODULO1;
				stringHash2 = (SYMBOLS * (stringHash2 - (symbolsPower2 * string[prevStartIndex] % MODULO2) + MODULO2) + string[it]) % MODULO2;

				if (patternHash1 == stringHash1 && patternHash2 == stringHash2) {
					++matches;
					if (matchesStart.size() < 1000)
						matchesStart.add(prevStartIndex + 1);
				}
			}

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

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

}