Cod sursa(job #2067251)

Utilizator turbowin120Amarandei-Stanescu Alexandru turbowin120 Data 16 noiembrie 2017 01:59:40
Problema Potrivirea sirurilor Scor 40
Compilator java Status done
Runda Arhiva educationala Marime 4.32 kb


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

class Main {

    static int[][] calculatePrefixes(String[] toFind) {
        int pref[][] = new int[toFind.length][];
        for (int i = 0; i < pref.length; i++) {
            pref[i] = new int[toFind[i].length()];
        }

        for (int i = 0; i < pref.length; i++) {
            int k = 0;
            pref[i][1] = pref[i][0] = 0;
            for (int j = 2; j < pref[i].length; j++) {
                while(k > 0 && toFind[i].charAt(k + 1) != toFind[i].charAt(j)) {
                    k = pref[i][k];
                }
                if (toFind[i].charAt(k + 1) == toFind[i].charAt(j)) {

                    k++;
                }
                pref[i][j] = k;
            }
        }
        return pref;
    }

    static void getKMP(int[][] pref, String[] toFind, String fromThis) {

        int[] k = new int[toFind.length];
        for (int i = 0; i < k.length; i++) {
            k[i] = 0;
        }
        int solutions = 0;
        int solpos[];
        solpos = new int[1002];
        //System.out.println(fromThis.charAt(475)+  " " + fromThis.charAt(476));
        for (int i = 1; i < fromThis.length() && solutions < 1001; i++) {
            for (int j = 0; j < k.length && solutions < 1001; j++) {
                //System.out.println(toFind[j].charAt(k[j]) + " " + k[j]+ " ");
                while (k[j] > 0 && toFind[j].charAt(k[j] + 1) != fromThis.charAt(i)) {
                    k[j] = pref[j][k[j]];
                }
                 //System.out.println(toFind[j].charAt(k[j] + 1) + " "+ fromThis.charAt(i) + " " + k[j] + " " + i);
                if (toFind[j].charAt(k[j] + 1) == fromThis.charAt(i)) {
                   
                    k[j]++;
                }
                if (k[j] == toFind[j].length()-1) {
                    // System.out.println(i );
                    k[j] = pref[j][k[j]];
                    
                    if (solutions < 1001) {
                        solpos[solutions] = i - toFind[j].length() +1;
                        solutions++;
                    }

                }
            }
        }
        printToFile(solpos, solutions);
    }

    static void printToFile(int[] solpos, int sols) {

        try {
            String fileNameOut = "strmatch.out";
            BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(fileNameOut));
            bufferedWriter.write(sols + "\n");
            int min;
            if (sols > 1000) {
                min = 1000;
            } else {
                min = sols;
            }
            for (int i = 0; i < min; i++) {
                bufferedWriter.write(solpos[i] + " ");
            }
            bufferedWriter.flush();
            bufferedWriter.close();
        } catch (IOException ex) {

        }

    }

    public static void main(String args[]) {
        String fileNameIn = "strmatch.in";

        BufferedReader reader;
        try {
            reader = new BufferedReader(new FileReader(fileNameIn));
            String firstLine = reader.readLine();
            String[] stringToFind = firstLine.split(" ");
            for (int i = 0; i < stringToFind.length; i++) {
                stringToFind[i] = (" ").concat(stringToFind[i]);
            }
            String findInThis = reader.readLine();
            findInThis = (" ").concat(findInThis);
            //System.out.println(findInThis.length() + " " + stringToFind[0].length());

            int preficx[][] = calculatePrefixes(stringToFind);
            getKMP(preficx, stringToFind, findInThis);
            //printArray(preficx);
            //System.out.println("It worked");
            reader.close();
        } catch (FileNotFoundException ex) {
            System.out.println("Error");
        } catch (IOException ex) {
            System.out.println("Error");
        }

    }

    static void printArray(int[][] toPrint) {

        for (int i = 0; i < toPrint.length; i++) {
            for (int j = 0; j < toPrint[i].length; j++) {
                System.out.print(toPrint[i][j] + " ");
            }
            System.out.println("\n");
        }
    }

}