Cod sursa(job #1765039)

Utilizator UTCN_FrunzaUTCN Lazar Nitu Petruta UTCN_Frunza Data 26 septembrie 2016 11:08:05
Problema Potrivirea sirurilor Scor 40
Compilator java Status done
Runda Arhiva educationala Marime 3.19 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 {

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

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

		}

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

			}

		}

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

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

	}

}