Cod sursa(job #2229397)

Utilizator radustn92Radu Stancu radustn92 Data 6 august 2018 17:46:44
Problema Potrivirea sirurilor Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 3.53 kb
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        InputStream inputStream = new FileInputStream("strmatch.in");
        OutputStream outputStream = new FileOutputStream("strmatch.out");

        try (InputReader inputReader = new InputReader(inputStream);
            PrintWriter printWriter = new PrintWriter(outputStream)) {
            String smallString = inputReader.nextToken();
            String largeString = inputReader.nextToken();

            Solver.solve(smallString.toCharArray(), largeString.toCharArray(), printWriter);
        }
    }

    static class Solver {

        private static int[] largestPrefixSuffix(char[] str) {
            int[] result = new int[str.length];
            Arrays.fill(result, -1);

            int longestPrefixSuffix = -1;
            for (int idx = 1; idx < str.length; idx++) {
                while (longestPrefixSuffix != -1 && str[longestPrefixSuffix + 1] != str[idx]) {
                    longestPrefixSuffix = result[longestPrefixSuffix];
                }

                if (str[longestPrefixSuffix + 1] == str[idx]) {
                    longestPrefixSuffix++;
                }

                result[idx] = longestPrefixSuffix;
            }

            return result;
        }

        public static void solve(char[] smallString, char[] largeString, PrintWriter printWriter) {
            int[] longestPrefixSuffix = largestPrefixSuffix(smallString);

            int longestSuffixMatch = -1, countMatches = 0;
            int[] topThousandMatches = new int[1000];
            for (int idx = 0; idx < largeString.length; idx++) {
                while (longestSuffixMatch != -1 && smallString[longestSuffixMatch + 1] != largeString[idx]) {
                    longestSuffixMatch = longestPrefixSuffix[longestSuffixMatch];
                }

                if (smallString[longestSuffixMatch + 1] == largeString[idx]) {
                    longestSuffixMatch++;
                }

                if (longestSuffixMatch == smallString.length - 1) {
                    if (countMatches < 1000) {
                        topThousandMatches[countMatches] = idx - smallString.length + 1;
                    }
                    countMatches++;
                    longestSuffixMatch = longestPrefixSuffix[longestSuffixMatch];
                }
            }

            printWriter.println(countMatches);
            for (int matchNo = 0, totalMatches = Math.min(1000, countMatches); matchNo < totalMatches; matchNo++) {
                printWriter.print(topThousandMatches[matchNo] + " ");
            }
            printWriter.println();
        }
    }

    static class InputReader implements AutoCloseable {

        private BufferedReader bufferedReader;

        private StringTokenizer stringTokenizer;

        public InputReader(InputStream inputStream) {
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
            stringTokenizer = null;
        }

        private String nextToken() {
            if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return stringTokenizer.nextToken();
        }

        @Override
        public void close() throws IOException {
            bufferedReader.close();
        }
    }
}