Cod sursa(job #2207262)

Utilizator VNohaiNohai Vlad-Auras VNohai Data 25 mai 2018 13:30:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <string.h>
using namespace std;
char a[2000005], b[2000005];
int af[2000005];
int has, hbs, c=0, p=1;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

bool ok(int i)
{
   for(int j=0; j<strlen(b); j++)
    if(b[j]!=a[i+j]) return 0;
   return 1;
}

int main()
{
    f>>b;
    f>>a;
    if(strlen(b)>strlen(a)) {g<<"0"; return 0;}
    for(int i=0; i<strlen(b); i++)
    {hbs=((hbs*73)+b[i])%101;
     has=((has*73)+a[i])%101;
     if(i) p=(p*73);
     if(i!=(strlen(b)-1)) p=p%101;}

    for(int i=0; i<=strlen(a)-strlen(b); i++)
    {
    if(has==hbs)
    if(ok(i))
    {c++; af[c]=i;}
    has=((has+101-((a[i]*(p))%101))*73+a[i+strlen(b)])%101;
    }
    g<<c<<'\n';
    for(int i=1; i<=c; i++) g<<af[i]<<" ";
    return 0;
}