Pagini recente » Cod sursa (job #2980561) | Cod sursa (job #3040907) | Cod sursa (job #2961538) | Cod sursa (job #159169) | Cod sursa (job #2260556)
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
public class RollingHash {
private static final String INPUT_FILE_PATH = "strmatch.in";
private static final String OUTPUT_FILE_PATH = "strmatch.out";
private static final int PRIME = 666013;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new FileReader(INPUT_FILE_PATH));
String s0 = bf.readLine();
String s1 = bf.readLine();
ArrayList<Integer> matches = RollingHash.match(s0, s1);
PrintWriter pw = new PrintWriter(OUTPUT_FILE_PATH);
pw.println(matches.size());
matches.forEach((m) -> pw.print(m + " "));
pw.flush();
}
private static ArrayList<Integer> match(String s0, String s1) {
s0 = s0.toLowerCase();
s1 = s1.toLowerCase();
long hash0 = 0;
long hash1 = 0;
long base = 256;
long biggestPOW = 1;
for (int i = 0; i < s0.length(); ++i) {
hash0 = (base * hash0 + s0.charAt(i)) % PRIME;
hash1 = (base * hash1 + s1.charAt(i)) % PRIME;
if (i != 0) {
biggestPOW = (biggestPOW * base) % PRIME;
}
}
ArrayList<Integer> matches = new ArrayList<>();
int it = s0.length();
do {
if (hash0 == hash1) {
matches.add(it - s0.length());
}
hash1 = ((hash1 + PRIME - (s1.charAt(it - s0.length()) * biggestPOW) % PRIME) * base + s1.charAt(it)) % PRIME;
++it;
} while (it < s1.length());
return matches;
}
}