Pagini recente » Cod sursa (job #968965) | Cod sursa (job #2940353) | Cod sursa (job #1286141) | Cod sursa (job #2839541) | Cod sursa (job #1765022)
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() {
Scanner scanner = new Scanner(Main.class.getResourceAsStream("strmatch.in"));
whatToSearch = scanner.nextLine();
whereToSearch = scanner.nextLine();
}
private static void writeOutput(Result result) throws FileNotFoundException {
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]);
}
}
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;
}
}
}