Cod sursa(job #1765025)

Utilizator UTCN_FrunzaUTCN Lazar Nitu Petruta UTCN_Frunza Data 26 septembrie 2016 10:40:08
Problema Potrivirea sirurilor Scor 40
Compilator java Status done
Runda Arhiva educationala Marime 3.09 kb
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	private static String whatToSearch;
	private static String whereToSearch;

	public static void main(String[] args) throws Exception {
		readInput();

		SearchEngine searchEngine = new SearchEngine();

		Result output = searchEngine.search(whatToSearch, whereToSearch);
		writeOutput(output);

	}

	private static void readInput() throws Exception {
		Scanner scanner = new Scanner(new FileInputStream("strmatch.in"));
		whatToSearch = scanner.nextLine();
		whereToSearch = scanner.nextLine();

	}

	private static void writeOutput(Result result) throws Exception {
		PrintWriter stream = new PrintWriter("strmatch.out");
		stream.printf("%d\n", result.getNumberOfOccurrences());
		for (int i = 0; i < result.getNumberOfOccurrences(); i++) {
			stream.printf("%d ", result.getOccurrencePositions()[i]);
		}
		stream.close();

	}

	public static class Result {

		private int numberOfOccurrences;

		private int[] occurrencePositions;

		public Result(int numberOfOccurrences, int[] occurrencePositions) {
			this.numberOfOccurrences = numberOfOccurrences;
			this.occurrencePositions = occurrencePositions;
		}

		public Result() {
		}

		public int getNumberOfOccurrences() {
			return numberOfOccurrences;
		}

		public void setNumberOfOccurrences(int numberOfOccurrences) {
			this.numberOfOccurrences = numberOfOccurrences;
		}

		public int[] getOccurrencePositions() {
			return occurrencePositions;
		}

		public void setOccurrencePositions(int[] occurrencePositions) {
			this.occurrencePositions = occurrencePositions;
		}
	}

	public static class SearchEngine {

		List<Integer> occurences = new ArrayList<Integer>();
		public static final int SIZE = 2000005;
		int prefix[] = new int[SIZE];

		public void computePrefix(String value) {
			prefix[1] = 0;
			int k = 0;
			for (int i = 2; i < value.length(); i++) {
				while (k > 0 && (value.charAt(i) != value.charAt(k + 1))) {
					k = prefix[k];
				}
				if (value.charAt(i) == value.charAt(k + 1)) {
					k = k + 1;
				}
				prefix[i] = k;
			}

		}

		public void potrivire(String base, String result) {
			int q = 0;
			for (int i = 0; i < result.length(); i++) {
				while (q > 0 && (result.charAt(i) != base.charAt(q + 1))) {
					q = prefix[q];
				}
				if (result.charAt(i) == base.charAt(q + 1)) {
					q++;
				}
				if (q == base.length() - 2) {
					q = prefix[q];
					occurences.add(i - (base.length() - 2));
				}

			}

		}

		public Main.Result search(String whatToSearch, String whereToSearch) {
			whatToSearch = " " + whatToSearch;
			whereToSearch = " " + whereToSearch;
			computePrefix(whatToSearch);
			whatToSearch = whatToSearch + " ";
			potrivire(whatToSearch, whereToSearch);
			Main.Result result = new Main.Result();
			result.setNumberOfOccurrences(occurences.size());

			int res[] = new int[occurences.size()];
			for (int i = 0; i < occurences.size(); i++) {
				res[i] = occurences.get(i);
			}
			result.setOccurrencePositions(res);
			return result;
		}

	}

}