Cod sursa(job #2775659)

Utilizator manciu_ionIon Manciu manciu_ion Data 16 septembrie 2021 18:01:05
Problema Potrivirea sirurilor Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.32 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 {
    private String model;
    private String strToCompare;
    private int[] poz = new int[1001];

    public void readData() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new FileReader("strmatch.in"));
        StreamTokenizer streamTokenizer = new StreamTokenizer(bufferedReader);
        streamTokenizer.nextToken();
        model = streamTokenizer.sval;
        streamTokenizer.nextToken();
        strToCompare = streamTokenizer.sval;
        System.out.println(model + " " + strToCompare);
        final int[] prefix = makePrefix(model);

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

            if (strToCompare.charAt(i) == model.charAt(q)) {
                ++q;
            }

            if (q == model.length()) {
                poz[nrMatches++] = i - model.length() + 1;
                q = prefix[model.length() - 1];
                if (nrMatches >= 1000) {
                    break;
                }
            }
        }

        PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter("strmatch.out")));
        System.out.println(nrMatches);
        writer.println(nrMatches);
        for (int i = 0; i < nrMatches; i++) {
            if (i != 0) {
                writer.print(" ");
            }
            writer.print(poz[i]);
        }
        writer.close();
    }

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

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

        return phi;
    }

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

        new Main().readData();
    }
}