Pagini recente » Cod sursa (job #2634791) | Cod sursa (job #2867678) | Cod sursa (job #2125730) | Cod sursa (job #2126319) | Cod sursa (job #2775663)
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 {
private String model;
private String strToCompare;
private int[] poz = new int[1001];
public void readData() throws IOException {
BufferedReader bufferedReader = new BufferedReader(new FileReader("strmatch.in"));
StreamTokenizer streamTokenizer = new StreamTokenizer(bufferedReader);
streamTokenizer.nextToken();
model = streamTokenizer.sval;
streamTokenizer.nextToken();
strToCompare = streamTokenizer.sval;
System.out.println(model + " " + strToCompare);
final int[] prefix = makePrefix(model);
int nrMatches = 0;
for (int i = 0, q = 0; i < strToCompare.length(); i++) {
while (q > 0 && strToCompare.charAt(i) != model.charAt(q)) {
q = prefix[q - 1];
}
if (strToCompare.charAt(i) == model.charAt(q)) {
++q;
}
if (q == model.length()) {
poz[nrMatches++] = i - model.length() + 1;
q = prefix[model.length() - 1];
if (nrMatches >= 1000) {
break;
}
}
}
PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter("strmatch.out")));
System.out.println(nrMatches);
writer.println(nrMatches);
for (int i = 0; i < nrMatches; i++) {
if (i != 0) {
writer.print(" ");
}
writer.print(poz[i]);
}
writer.close();
}
public int[] makePrefix(String model) {
int[] phi = new int[model.length()];
phi[0] = 0;
for (int i = 1, q = 0; i < model.length(); i++) {
while (q > 0 && model.charAt(q) != model.charAt(i)) {
q = phi[q - 1];
}
if (model.charAt(q) == model.charAt(i)) {
++q;
}
phi[i] = q;
}
return phi;
}
public static void main(String[] args) throws IOException {
new Main().readData();
}
}