Pagini recente » Cod sursa (job #631303) | Cod sursa (job #1626909) | Cod sursa (job #1121816) | Cod sursa (job #678290) | Cod sursa (job #2067188)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.logging.Level;
import java.util.logging.Logger;
public class KMP {
public static int[][] calculatePrefixes(String[] toFind) {
int pref[][] = new int[toFind.length][];
for (int i = 0; i < pref.length; i++) {
pref[i] = new int[toFind[i].length()];
}
for (int i = 0; i < pref.length; i++) {
int k = 0;
pref[i][0] = 0;
for (int j = 1; j < pref[i].length; j++) {
if (k > 0 && toFind[i].charAt(k) != toFind[i].charAt(j)) {
k = pref[i][k];
}
if (toFind[i].charAt(k) == toFind[i].charAt(j)) {
k++;
}
pref[i][j] = k;
}
}
return pref;
}
public static void getKMP(int[][] pref, String[] toFind, String fromThis) {
int[] k = new int[toFind.length];
for (int i = 0; i < k.length; i++) {
k[i] = 0;
}
int solutions = 0;
int solpos[];
solpos = new int[1002];
for (int i = 0; i < fromThis.length() && solutions < 1001; i++) {
for (int j = 0; j < k.length && solutions < 1001; j++) {
if (k[j] > 0 && toFind[j].charAt(k[j]) != fromThis.charAt(i)) {
k[j] = pref[j][k[j]];
}
if (toFind[j].charAt(k[j]) == fromThis.charAt(i)) {
k[j]++;
}
if (k[j] == toFind[j].length()) {
solutions++;
if (solutions < 1001) {
solpos[solutions - 1] = i - toFind[j].length() + 1;
}
k[j] = pref[j][k[j] - 1];
}
}
}
printToFile(solpos, solutions);
}
public static void printToFile(int[] solpos, int sols) {
try {
String fileNameOut = "strmatch.out";
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(fileNameOut));
bufferedWriter.write(sols + "\n");
int min;
if(sols > 1000){
min = 1000;
}
else {
min = sols;
}
for (int i = 0; i < min; i++) {
bufferedWriter.write(solpos[i] + " ");
}
bufferedWriter.flush();
bufferedWriter.close();
} catch (IOException ex) {
Logger.getLogger(KMP.class.getName()).log(Level.SEVERE, null, ex);
}
}
public static void main(String[] args) {
String fileNameIn = "strmatch.in";
BufferedReader reader;
try {
reader = new BufferedReader(new FileReader(fileNameIn));
String firstLine = reader.readLine();
String[] stringToFind = firstLine.split(" ");
String findInThis = reader.readLine();
int preficx[][] = calculatePrefixes(stringToFind);
getKMP(preficx, stringToFind, findInThis);
reader.close();
} catch (FileNotFoundException ex) {
Logger.getLogger(KMP.class.getName()).log(Level.SEVERE, null, ex);
} catch (IOException ex) {
Logger.getLogger(KMP.class.getName()).log(Level.SEVERE, null, ex);
}
}
public static void printArray(int[][] toPrint) {
for (int i = 0; i < toPrint.length; i++) {
for (int j = 0; j < toPrint[i].length; j++) {
System.out.print(toPrint[i][j] + " ");
}
System.out.println("\n");
}
}
}