Cod sursa(job #3287874)

Utilizator lucky1992Ion Ion lucky1992 Data 19 martie 2025 16:32:30
Problema Potrivirea sirurilor Scor 40
Compilator java Status done
Runda Arhiva educationala Marime 2.03 kb
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
  public static final int BASE = 256;

  public static final long MOD_1 = 1_000_000_009;

  public static final long MOD_2 = 1_000_000_007;

  public static void main(String[] args) throws FileNotFoundException {
    try (Scanner scanner = new Scanner(new FileInputStream("strmatch.in"));
         PrintWriter pw = new PrintWriter(new FileOutputStream("strmatch.out"))) {
      String pattern = scanner.next();
      String str = scanner.next();

      int L = pattern.length();

//      System.out.println(pattern);
//      System.out.println(str);

      long hashPat1 = 0, hashPat2 = 0, magic1 = 1, magic2 = 1;

      for (int i = 0; i < pattern.length(); i++) {
        hashPat1 = (hashPat1 * BASE +  pattern.charAt(i)) % MOD_1;
        hashPat2 = (hashPat2 * BASE +  pattern.charAt(i)) % MOD_2;

        if (i > 0) {
          magic1 = (magic1 * BASE) % MOD_1;
          magic2 = (magic2 * BASE) % MOD_2;
        }
      }

      long hash1 = 0, hash2 = 0;

      List<Integer> sol = new ArrayList<>(2000);
      int occurrences = 0;

      for (int i = 0; i < str.length(); i++) {
        // SKIP
        if (i >= L) {
          hash1 = (hash1 - ((str.charAt(i - L) * magic1) % MOD_1) + MOD_1) % MOD_1;
          hash2 = (hash2 - ((str.charAt(i - L) * magic2) % MOD_2) + MOD_2) % MOD_2;
        }

        // APPEND
        hash1 = (hash1 * BASE + str.charAt(i)) % MOD_1;
        hash2 = (hash2 * BASE + str.charAt(i)) % MOD_2;

        if (i >= L - 1) {
          if (hash1 == hashPat1 && hash2 == hashPat2) {
            occurrences++;
            if (occurrences < 1001) {
              sol.add(i - L + 1);
            }

          }
        }
      }

      pw.println(occurrences);
      for (int i = 0; i < sol.size(); i++) {
        if (i != 0) {
          pw.print(" ");
        }
        pw.print(sol.get(i));
      }
    }
  }
}