Cod sursa(job #1914947)

Utilizator FredyLup Lucia Fredy Data 8 martie 2017 19:05:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

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

#define lim 2000010
#define base 73
#define mod1 100007
#define mod2 100021

char a[lim], b[lim];
int rez[lim],n,m,numar1,numar2;

int main()
{
    fin>>a;
    fin>>b;

    n=strlen(a);
    m=strlen(b);
    numar1=0, numar2=0;

    for(int i=0; i<n; i++)
    {
        numar1 = (numar1*base+a[i]) % mod1;
        numar2 = (numar2*base+a[i]) % mod2;
    }

   int nr1=0, nr2=0;
    if(n>m)
    {
        fout<<0;
        return 0;
    }

    int A1=1,B1=1;
    for(int i=0; i<n; i++)
    {
        nr1 = (nr1*base+b[i]) % mod1;
        nr2 = (nr2*base+b[i]) % mod2;

        if(i)
        {
            A1=(A1*base)%mod1;
            B1=(B1*base)%mod2;
        }
    }

    int dr=0;
    if(numar1==nr1 && numar2==nr2)
        rez[++dr]=0;



    for(int i=n; i<m; i++)
    {
        nr1 = ( ( nr1-(b[i-n]*A1)%mod1 + mod1 ) * base + b[i] ) % mod1;
        nr2 = ( ( nr2-(b[i-n]*B1)%mod2 + mod2 ) * base + b[i] ) % mod2;

        if(nr1==numar1 && nr2==numar2)
        {
            if(dr<1000)
                rez[++dr]=i-n+1;
            else dr++;
        }
    }

    fout<<dr<<'\n';

    int g=min(dr,1000);
    for(int i=1; i<=g; i++)
        fout<<rez[i]<<' ';

    fin.close();
    fout.close();
    return 0;
}