Pagini recente » Cod sursa (job #1836376) | Cod sursa (job #2619767) | Cod sursa (job #730439) | Diferente pentru implica-te/arhiva-educationala intre reviziile 182 si 181 | Cod sursa (job #3287883)
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
public static class MyScanner implements Closeable {
BufferedReader br;
StringTokenizer st;
public MyScanner(String file) throws FileNotFoundException {
br = new BufferedReader(new InputStreamReader(new FileInputStream(file)), 1 << 16);
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine(){
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
@Override
public void close() throws IOException {
br.close();
}
}
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 IOException {
try (MyScanner scanner = new MyScanner("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));
}
}
}
}