Pagini recente » Cod sursa (job #2325589) | Cod sursa (job #1154393) | Cod sursa (job #640911) | Cod sursa (job #2375426) | Cod sursa (job #1384190)
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
try {
Scanner sc = new Scanner(new File("strmatch.in"));
String N = sc.useDelimiter("\n").next();
String M = sc.useDelimiter("\n").next();
int[] prefixTable = prefixCalc(N);
int n = N.length();
int m = M.length();
String resultString = "";
int count = 0;
int q = -1;
for (int i = 0; i < m; i++) {
while (q > -1 && N.charAt(q + 1) != M.charAt(i)) {
q = prefixTable[q];
}
if (N.charAt(q + 1) == M.charAt(i)) {
q++;
}
if (q == n - 2) {
count++;
resultString += Integer.toString(i - n + 2) + " ";
}
}
PrintWriter pr = new PrintWriter("strmatch.out");
pr.println(count);
pr.println(resultString);
pr.close();
} catch (FileNotFoundException ex) {
ex.printStackTrace();
}
}
public static int[] prefixCalc(String N) {
int stringLegth = N.length();
int[] prefixTable = new int[stringLegth];
Arrays.fill(prefixTable, -1);
int k = -1;
prefixTable[0] = -1;
for (int i = 1; i < stringLegth; i++) {
while (k > -1 && N.charAt(k + 1) != N.charAt(i)) {
k = prefixTable[k];
}
if (N.charAt(k + 1) == N.charAt(i)) {
k++;
}
prefixTable[i] = k;
}
return prefixTable;
}
}