Cod sursa(job #1743591)

Utilizator AplayLazar Laurentiu Aplay Data 18 august 2016 14:02:08
Problema Potrivirea sirurilor Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 2.22 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 MODULO = 1999999973;

	private static long pow(long x, long power) {
		long answer = 1;

		while (power-- > 0) {
			answer *= x;
			answer %= MODULO;
		}

		return answer;
	}

	private static long[] hashString(String string, int sequenceLength) {
		long[] hashes = new long[string.length() - sequenceLength + 1];

		for (int it = 0; it < sequenceLength; ++it) {
			hashes[0] = ((SYMBOLS * hashes[0]) % MODULO + string.charAt(it)) % MODULO;
		}

		long power = pow(SYMBOLS, sequenceLength - 1);

		for (int it = sequenceLength; it < string.length(); ++it) {
			int index = it - sequenceLength;
			hashes[index + 1] = (SYMBOLS * (hashes[index] - ((power * string.charAt(index)) % MODULO) + MODULO )) % MODULO;
			hashes[index + 1] = (hashes[index + 1] + string.charAt(it)) % MODULO;		
		}

		return hashes;
	}

	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();

		if (pattern.length() > string.length()) {
			writer.write("0");
		} else {
			long[] hashes = hashString(string, pattern.length());
			long[] patternHash = hashString(pattern, pattern.length());

			long matches = 0;
			List<Integer> matchesStart = new ArrayList<>();

			for (int it = 0; it < hashes.length; ++it) {
				if (hashes[it] == patternHash[0]) {
					boolean isOk = true;
					for (int jt = 0; jt < pattern.length() && isOk; ++jt) {
						if (string.charAt(it + jt) != pattern.charAt(jt))
							isOk = false;
					}

					if (isOk) {
						++matches;
						if (matchesStart.size() < 1000) {
							matchesStart.add(it);
						}
					}
				}
			}

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

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

}