Pagini recente » Cod sursa (job #2632402) | Cod sursa (job #1570081) | Cod sursa (job #2860505) | Cod sursa (job #107893) | Cod sursa (job #2776464)
//package com.company;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main {
public void readData() throws IOException {
BufferedReader bufferedReader = new BufferedReader(new FileReader("strmatch.in"));
StreamTokenizer streamTokenizer = new StreamTokenizer(bufferedReader);
streamTokenizer.nextToken();
final char[] chars = streamTokenizer.sval.toCharArray();
final char[] model = new char[chars.length + 1];
System.arraycopy(chars, 0, model, 1, chars.length);
streamTokenizer.nextToken();
char[] strToCompare = streamTokenizer.sval.toCharArray();
char[] toCompare = new char[strToCompare.length + 1];
System.arraycopy(strToCompare, 0, toCompare, 1, strToCompare.length);
final int[] prefix = makePrefix(model);
final int[] poz = new int[1001];
int nrMatches = 0;
for (int i = 1, q = 0; i < toCompare.length; i++) {
while (q > 0 && toCompare[i] != model[q + 1]) {
q = prefix[q];
}
if (toCompare[i] == model[q + 1]) {
++q;
}
if (q == model.length - 1) {
nrMatches++;
q = prefix[model.length - 1];
if (nrMatches <= 1000) {
poz[nrMatches] = i - model.length + 1;
}
}
}
PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter("strmatch.out")));
writer.println(nrMatches);
for (int i = 1; i <= Math.min(1000, nrMatches) ; i++) {
writer.print(poz[i] + " ");
}
writer.flush();
writer.close();
}
public int[] makePrefix(char[] model) {
int[] phi = new int[model.length];
phi[1] = 0;
for (int i = 2, q = 0; i < model.length; i++) {
while (q > 0 && model[q + 1] != model[i]) {
q = phi[q];
}
if (model[q + 1] == model[i]) {
++q;
}
phi[i] = q;
}
return phi;
}
public static void main(String[] args) throws IOException {
new Main().readData();
}
}