Pagini recente » Cod sursa (job #650660) | Cod sursa (job #621687) | Cod sursa (job #462305) | Cod sursa (job #2919444) | Cod sursa (job #3287874)
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static final int BASE = 256;
public static final long MOD_1 = 1_000_000_009;
public static final long MOD_2 = 1_000_000_007;
public static void main(String[] args) throws FileNotFoundException {
try (Scanner scanner = new Scanner(new FileInputStream("strmatch.in"));
PrintWriter pw = new PrintWriter(new FileOutputStream("strmatch.out"))) {
String pattern = scanner.next();
String str = scanner.next();
int L = pattern.length();
// System.out.println(pattern);
// System.out.println(str);
long hashPat1 = 0, hashPat2 = 0, magic1 = 1, magic2 = 1;
for (int i = 0; i < pattern.length(); i++) {
hashPat1 = (hashPat1 * BASE + pattern.charAt(i)) % MOD_1;
hashPat2 = (hashPat2 * BASE + pattern.charAt(i)) % MOD_2;
if (i > 0) {
magic1 = (magic1 * BASE) % MOD_1;
magic2 = (magic2 * BASE) % MOD_2;
}
}
long hash1 = 0, hash2 = 0;
List<Integer> sol = new ArrayList<>(2000);
int occurrences = 0;
for (int i = 0; i < str.length(); i++) {
// SKIP
if (i >= L) {
hash1 = (hash1 - ((str.charAt(i - L) * magic1) % MOD_1) + MOD_1) % MOD_1;
hash2 = (hash2 - ((str.charAt(i - L) * magic2) % MOD_2) + MOD_2) % MOD_2;
}
// APPEND
hash1 = (hash1 * BASE + str.charAt(i)) % MOD_1;
hash2 = (hash2 * BASE + str.charAt(i)) % MOD_2;
if (i >= L - 1) {
if (hash1 == hashPat1 && hash2 == hashPat2) {
occurrences++;
if (occurrences < 1001) {
sol.add(i - L + 1);
}
}
}
}
pw.println(occurrences);
for (int i = 0; i < sol.size(); i++) {
if (i != 0) {
pw.print(" ");
}
pw.print(sol.get(i));
}
}
}
}