Cod sursa(job #2083368)

Utilizator sebi_andrei2008Lazar Eusebiu sebi_andrei2008 Data 7 decembrie 2017 17:08:11
Problema Potrivirea sirurilor Scor 4
Compilator java Status done
Runda Arhiva educationala Marime 2.67 kb
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    private static PrintWriter printWriter;
    private static MyScanner scanner;
    private static final long prime = 3;
    private static long childHash;
    private static int childLength;
    private static int parentLength;
    private static List<Integer> output = new ArrayList<>();

    private static long hash(String input) {
        long h = 0;

        for (int i = 0; i < input.length(); i++) {
            h += ((int) input.charAt(i)) * Math.pow(prime, i);
        }

        return h;
    }

    private static long nextHash(char oldChar, char nextChar, long oldHash, int length) {
        return (long) ((oldHash - (int) oldChar)/prime + ((int) nextChar) * Math.pow(prime, length - 1));
    }

    public static void main(String[] args) throws IOException {
        scanner = new MyScanner("strmatch.in");
        printWriter = new PrintWriter("strmatch.out");

        String child = scanner.next();
        String parent = scanner.next();

        childHash = hash(child);
        childLength = child.length();
        parentLength = parent.length();

        if (parentLength < childLength) {
            printWriter.printf("0");
            return;
        }

        long h = hash(parent.substring(0, childLength));
        if (h == childHash)
            output.add(0);

        for (int i = childLength; i < parentLength; i++) {
            h = nextHash(parent.charAt(i - childLength), parent.charAt(i), h, childLength);
            if (h == childHash)
                output.add(i - childLength + 1);
        }

        printWriter.printf("%d\n", output.size());

        int size = output.size();
        if (size > 1000)
            size = 1000;

        for (int i = 0; i < size; i++)
            printWriter.printf("%d ", output.get(i));

        printWriter.close();
        scanner.close();
    }

    private static class MyScanner
    {
        private BufferedReader bufferedReader;
        private StringTokenizer stringTokenizer;

        MyScanner(String filename) throws FileNotFoundException {
            bufferedReader = new BufferedReader(new FileReader(filename));
        }

        private String next() throws IOException {
            while(stringTokenizer == null || !stringTokenizer.hasMoreElements()) {
                stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            }
            return stringTokenizer.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt( next() );
        }

        void close() throws IOException {
            bufferedReader.close();
        }
    }
}