Cod sursa(job #2776307)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 19 septembrie 2021 11:51:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <string>

#define inout(f) std::ifstream in((f) + (std::string) ".in");std::ofstream out((f) + (std::string) ".out")
#define d(x) std::cout << x << std::endl
#define dm(msg, x) std::cout << msg << x << std::endl

const int NMAX = 2e6;

int z[2 + 2 * NMAX];

std::string a, b;

int cnt = 0;
int sol[1000];

int main() {
  inout("strmatch");

  in >> a >> b;

  int target = a.size();

  a = a + "." + b; // ABA.CABBCABABAB  

  int left = 0, right = 0;
  for (int i = 1; i < a.size(); ++i) {
    if (i > right) {
      left = right = i;

      while (right < a.size() && a[right - left] == a[right]) 
        ++right;

      z[i] = right - left;
      --right;
    }
    else {
      int _i = i - left;

      if (z[_i] < right - i + 1)
        z[i] = z[_i];

      else {
        left = i;
        while (right < a.size() && a[right - left] == a[right]) 
        ++right;

        z[i] = right - left;
        --right;
      }
    }
  }

  for (int i = 1; i < a.size(); ++i) {
    if (z[i] == target) {
      if (cnt < 1000)
        sol[cnt] = i - target - 1;

      ++cnt;
    }
  }

  out << cnt << '\n';
  for (int i = 0; i < std::min(1000, cnt); ++i)
    out << sol[i] << ' ';
  out << '\n';

  return 0;
}