Cod sursa(job #1904988)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 5 martie 2017 21:07:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <cstring>
#define Nmax 2000001
#define MOD1 1007
#define MOD2 1071
#define LL long long
#define base 71
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int n,NA,NB,rez[1001],nr;
int hash1, hash2,p1,p2;
char A[Nmax],B[Nmax];
int main()
{
    f>>A>>B;
    NA = strlen(A);
    NB = strlen(B);

    p1 = p2 = 1;
    for (int i=0;i<NA;i++)
    {
        hash1 = ((hash1*base) + A[i]) % MOD1;
        hash2 = ((hash2*base) + A[i]) % MOD2;
        if (i!=0)
        {
            p1 = p1 * base % MOD1;
            p2 = p2 * base % MOD2;
        }
    }

    if (NA>NB)
    {
        g<<0;
        return 0;
    }
    int H1 = 0,H2 = 0;
    for (int i=0;i<NA;i++)
    {
        H1 = ((H1 * base) + B[i]) % MOD1;
        H2 = ((H2 * base) + B[i]) % MOD2;
    }

    if (H1 == hash1 && H2 ==hash2)
        rez[++nr] = 0;

    for (int i=NA;i<NB;i++)
    {
        H1 = (((H1 - (p1 * B[i-NA]) % MOD1) + MOD1) * base + B[i]) % MOD1;
        H2 = (((H2 - (p2 * B[i-NA]) % MOD2) + MOD2) * base + B[i]) % MOD2;
        if (H1 == hash1 && H2 == hash2)
        {
            nr++;
            if (nr<=1000)
                rez[nr] = i-NA+1;
        }
    }
    g<<nr<<'\n';
    for (int i=1;i<=nr && i<=1000;i++,g<<' ')
        g<<rez[i];
    return 0;
}