Cod sursa(job #1743147)

Utilizator AplayLazar Laurentiu Aplay Data 17 august 2016 17:33:22
Problema Potrivirea sirurilor Scor 2
Compilator java Status done
Runda Arhiva educationala Marime 1.9 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 int SYMBOLS = 52;
	private static int MODULO = 1999999973;
	
	private static int pow(int x, int power) {
		int answer = 1;
		
		while (power-- > 0) {
			answer *= x;
			answer %= MODULO;
		}
		
		return answer;
	}
	
	private static int[] hashString(String string, int sequenceLength) {
		int[] hashes = new int[string.length() - sequenceLength + 1];
		
		for (int it = 0; it < sequenceLength; ++it) {
			hashes[0] = ((SYMBOLS * hashes[0]) % MODULO + (int) string.charAt(it)) % MODULO;
		}
		
		int power = pow(SYMBOLS, sequenceLength - 1);
		
		for (int it = sequenceLength; it < string.length(); ++it) {
			hashes[it - sequenceLength + 1] = (SYMBOLS * (hashes[it - sequenceLength] - power * string.charAt(it - sequenceLength) % MODULO) 
													+ (int) 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();
		
		int[] hashes = hashString(string, pattern.length());
		int[] patternHash = hashString(pattern, pattern.length());
		
		int matches = 0;
		List<Integer> matchesStart = new ArrayList<>();
		
		for (int it = 0; it < hashes.length; ++it) {
			if (hashes[it] == patternHash[0]) {
				++matches;
				if (matchesStart.size() < 1000) {
					matchesStart.add(it);
				}
			}
		}
		
		writer.write(matches + "\n");
		for (Integer it : matchesStart) {
			writer.write(it + " ");
		}
		
		reader.close();
		writer.close();
	}
	
}