Cod sursa(job #3329007)

Utilizator BiceaToader David Stefan Bicea Data 11 decembrie 2025 15:29:49
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,lps[2000001],nr,k,v[1001];
char a[2000001],b[2000001];
void calc()
{
  k=0;
  for(int i=1;i<=n-1;++i)
  {
    while(k && a[k]!=a[i-1]) k=lps[k];
    if(a[k]==a[i-1]) k++;
    lps[i]=k;
  }
}
void gasire()
{
  k=0;
  for(int i=0;i<=m-1;++i)
  {
    while(k && a[k]!=b[i]) k=lps[k];
    if(a[k]==b[i]) k++;
    if(k==n)
    {nr++;
      if(nr<1000) v[nr]=i-n+1;
    }
  }
}
void afisare()
{g<<nr<<'\n';
  for(int i=1;i<=min(nr,1000);++i)
    g<<v[i]<<" ";
}
int main()
{
   f.getline(a,2000001);
   f.getline(b,2000001);
    calc();
    gasire();
    afisare();
    return 0;
}