Cod sursa(job #2067205)

Utilizator turbowin120Amarandei-Stanescu Alexandru turbowin120 Data 16 noiembrie 2017 00:08:19
Problema Potrivirea sirurilor Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.7 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;
import java.util.logging.Level;
import java.util.logging.Logger;


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][0] = 0;
            for (int j = 1; j < pref[i].length; j++) {
                if (k > 0 && toFind[i].charAt(k) != toFind[i].charAt(j)) {
                    k = pref[i][k];
                }
                if (toFind[i].charAt(k) == 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];
        for (int i = 0; i < fromThis.length() && solutions < 1001; i++) {
            for (int j = 0; j < k.length && solutions < 1001; j++) {
                if (k[j] > 0 && toFind[j].charAt(k[j]) != fromThis.charAt(i)) {
                    k[j] = pref[j][k[j]];
                }
                if (toFind[j].charAt(k[j]) == fromThis.charAt(i)) {
                    k[j]++;
                }
                if (k[j] == toFind[j].length()) {
                    solutions++;
                    if (solutions < 1001) {
                        solpos[solutions - 1] = i - toFind[j].length() + 1;
                    }
                    k[j] = pref[j][k[j] - 1];
                }
            }
        }
        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) {
            
        }

    }

    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(" ");
            String findInThis = reader.readLine();

            int preficx[][] = calculatePrefixes(stringToFind);
            getKMP(preficx, stringToFind, findInThis);
            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");
        }
    }

}