Cod sursa(job #3287883)

Utilizator lucky1992Ion Ion lucky1992 Data 19 martie 2025 16:51:17
Problema Potrivirea sirurilor Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 2.89 kb
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
  public static class MyScanner implements Closeable {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner(String file) throws FileNotFoundException {
      br = new BufferedReader(new InputStreamReader(new FileInputStream(file)), 1 << 16);
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine(){
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }

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

  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 IOException {
    try (MyScanner scanner = new MyScanner("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));
      }
    }
  }
}