Cod sursa(job #2776461)

Utilizator manciu_ionIon Manciu manciu_ion Data 19 septembrie 2021 21:17:42
Problema Potrivirea sirurilor Scor 24
Compilator java Status done
Runda Arhiva educationala Marime 2.45 kb
//package com.company;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {

    public void readData() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new FileReader("strmatch.in"));
        StreamTokenizer streamTokenizer = new StreamTokenizer(bufferedReader);
        streamTokenizer.nextToken();
        final char[] chars = streamTokenizer.sval.toCharArray();
        final char[] model = new char[chars.length + 1];
        System.arraycopy(chars, 0, model, 1, chars.length);
        streamTokenizer.nextToken();
        char[] strToCompare = streamTokenizer.sval.toCharArray();
        char[] toCompare = new char[strToCompare.length + 1];
        System.arraycopy(strToCompare, 0, toCompare, 1, strToCompare.length);
        final int[] prefix = makePrefix(model);

        int nrMatches = 0;
        StringBuilder stringBuilder = new StringBuilder();

        for (int i = 1, q = 0; i < toCompare.length; i++) {
            while (q > 0 && toCompare[i] != model[q + 1]) {
                q = prefix[q];
            }

            if (toCompare[i] == model[q + 1]) {
                ++q;
            }

            if (q == model.length - 1) {
                nrMatches++;
                q = prefix[model.length - 1];
                if (nrMatches <= 1000) {
                    stringBuilder.append(i - model.length + 1).append(" ");
                }
            }
        }

        PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter("strmatch.out")));
        //System.out.println(nrMatches);
        //System.out.println(stringBuilder.toString());
        writer.println(nrMatches);
        writer.println(stringBuilder.toString());
        writer.flush();
        writer.close();
    }

    public int[] makePrefix(char[] model) {
        int[] phi = new int[model.length];
        phi[1] = 0;
        for (int i = 2, q = 0; i < model.length; i++) {
            while (q > 0 && model[q + 1] != model[i]) {
                q = phi[q];
            }

            if (model[q + 1] == model[i]) {
                ++q;
            }
            phi[i] = q;
        }

        return phi;
    }

    public static void main(String[] args) throws IOException {

        new Main().readData();
    }
}