Cod sursa(job #1867721)

Utilizator i_vlad17Vlad Alecu i_vlad17 Data 4 februarie 2017 11:55:04
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>
#define B1 101
#define B2 109
#define MOD1 666013
#define MOD2 10003

using namespace std;

char X[2000020],Y[2000020];
int a[2000020],v1,v2,h1,h2,n,m,p1,p2,i,nr;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

int main()
{
    f>>X;
    f>>Y;

    m = strlen(X);
    n = strlen(Y);

//    if ( m > n )
 //   {
 //       g<<0;
 //       return 0;
 //   }

    p1=p2=1;
    v1=v2=0;

    for (i=0; i<m; i++)
    {
        v1 = ( v1 * B1 + X[i]) % MOD1;
        v2 = ( v2 * B2 + X[i]) % MOD2;

        if ( i!=0 )
        {
            p1 = ( p1 * B1 ) % MOD1;
            p2 = ( p2 * B2 ) % MOD2;
        }
    }

    h1=h2=0;

    for (i=0; i<m; i++)
    {
        h1 = ( h1 * B1 + Y[i]) % MOD1;
        h2 = ( h2 * B2 + Y[i]) % MOD2;
    }

    if (h1 == v1 && h2 == v2)
    {
        nr++;
        a[0] = 0;
    }

    for (i=m; i<n; i++)
    {
        h1 = ((h1 - (Y[i - m] * p1) % MOD1 + MOD1) * B1 + Y[i] ) % MOD1;
        h2 = ((h2 - (Y[i - m] * p2) % MOD2 + MOD2) * B2 + Y[i] ) % MOD2;
        if (h1 == v1 && h2 == v2)
        {
            nr++;
            a[i - m +1] = 1;
        }
    }
    g<<nr<<'\n';
    if(n<1000)
    {
        for (i = 0; i < n; i++)
            if (a[i])
                g<<i<<" ";
    }
    else
    {
        for (i = 0; i < 1000; i++)
            if (a[i])
                g<<i<<" ";
    }

    return 0;
}