Cod sursa(job #1384190)

Utilizator stefan.vascoVanea Stefan Vascocenco stefan.vasco Data 10 martie 2015 22:23:34
Problema Potrivirea sirurilor Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.85 kb
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        try {
            Scanner sc = new Scanner(new File("strmatch.in"));
            String N = sc.useDelimiter("\n").next();
            String M = sc.useDelimiter("\n").next();

            int[] prefixTable = prefixCalc(N);
            int n = N.length();
            int m = M.length();
            String resultString = "";
            int count = 0;

            int q = -1;
            for (int i = 0; i < m; i++) {
                while (q > -1 && N.charAt(q + 1) != M.charAt(i)) {
                    q = prefixTable[q];
                }

                if (N.charAt(q + 1) == M.charAt(i)) {
                    q++;
                }

                if (q == n - 2) {
                    count++;
                    resultString += Integer.toString(i - n + 2) + " ";
                }
            }

            PrintWriter pr = new PrintWriter("strmatch.out");
            pr.println(count);
            pr.println(resultString);
            pr.close();

        } catch (FileNotFoundException ex) {
           ex.printStackTrace();
        }
    }

    public static int[] prefixCalc(String N) {
        int stringLegth = N.length();
        int[] prefixTable = new int[stringLegth];
        Arrays.fill(prefixTable, -1);
        int k = -1;
        prefixTable[0] = -1;
        for (int i = 1; i < stringLegth; i++) {
            while (k > -1 && N.charAt(k + 1) != N.charAt(i)) {
                k = prefixTable[k];
            }

            if (N.charAt(k + 1) == N.charAt(i)) {
                k++;
            }

            prefixTable[i] = k;
        }
        return prefixTable;
    }

}