Cod sursa(job #2260556)

Utilizator abitlazyabitlazy abitlazy Data 15 octombrie 2018 09:50:03
Problema Potrivirea sirurilor Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.72 kb
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;
    }
}