Pagini recente » Cod sursa (job #594545) | Cod sursa (job #973725) | Cod sursa (job #177019) | Cod sursa (job #423825) | Cod sursa (job #2059909)
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.io.PrintWriter;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws FileNotFoundException, IOException {
Scanner in = new Scanner(new BufferedReader(new FileReader("strmatch.in")));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("strmatch.out")));
String a = in.next();
String b = in.next();
//we need to find a in b
int[] pre = new int[a.length()]; //pre[i] = the longest prefix of substring [0..i] that is also a proper suffix of [0..i]
pre[0] = 0;
int i = 1; //we are evaluating pre[i] (i is index where suffix ends)
int j = 0; //j is index where prefix ends
while (i < a.length()) {
if (a.charAt(i) == a.charAt(j)) {
pre[i] = j + 1;
i++;
j++;
} else {
if (j == 0) {
pre[i] = 0;
i++;
} else {
j = pre[j - 1];
}
}
}
// for (int k = 0; k < pre.length; k++) {
// System.out.print(pre[k] + " ");
// }
// System.out.println();
i = 0; //now i is the index in the pattern
j = 0; //now j is the index in the big string (can never decrease)
int sol = 0; //no. of solutions
int[] poz = new int[1000];
while (j < b.length()) {
// System.out.println(i + " and " + j);
if (a.charAt(i) == b.charAt(j)) {
i++;
j++;
if (i == a.length()) {
i = pre[i - 1];
sol++;
if (sol <= 1000) {
poz[sol - 1] = j - a.length();
// System.out.println(" => sol " + sol + ": " + poz[sol - 1]);
}
}
} else {
if (i == 0) {
j++;
} else {
i = pre[i - 1];
}
}
}
out.println(sol);
i = 0;
while (i < sol && i < 1000) {
out.print(poz[i] + " ");
i++;
}
in.close();
out.close();
}
}