Cod sursa(job #3340593)

Utilizator Gerald123Ursan George Gerald123 Data 15 februarie 2026 11:02:48
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
/// patratele
#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000003
#define NMAX 2000005

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int i, pi[NMAX], la, lb, pib[NMAX], ras[NMAX], vf;
char a[NMAX], b[NMAX];

void py()
{
  la = strlen(a);
  int k = 0;
  for (i = 1; i < la; i++)
  {
    while (k != 0 && a[k] != a[i])
      k = pi[k - 1];
    if (a[k] == a[i])
      k++;
    pi[i] = k;
  }
}

int main()
{
  // ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  fin >> a >> b;
  py();
  lb = strlen(b);
  int k = 0;
  for (i = 0; i < lb; i++)
  {
    while (k!=0 && a[k] != b[i])
      k = pi[k - 1];
    if (a[k] == b[i])
      k++;
    //pib[i] = k;
    if (pi[i] == la)
      ras[++vf] = i - la + 1;
  }
  fout << vf << '\n';
  for (i = 1; i <= min(1000, vf); i++)
    fout << ras[i] << " ";
  return 0;
}