Cod sursa(job #1814217)

Utilizator rangalIstrate Sebastian rangal Data 23 noiembrie 2016 19:19:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <cstdio>
#include <iostream>
#include <cstring>
#define lgmax 2000003
#define in "strmatch.in"
#define out "strmatch.out"
#define base 73
#define mod 100007
#define mod2 100021

typedef unsigned long long ull;

using namespace std;

ull Mx,Mx2;
ull hashA1,hashA2,hash1,hash2;
char A[lgmax],B[lgmax];
bool match[lgmax];

int m,n;

int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);

    scanf("%s %s",A,B);

    m=strlen(A);
    n=strlen(B);

    Mx=Mx2=1;
    hashA1=hashA2=0;

    for(int i=0; i<m; ++i)
    {
        hashA1=(hashA1*base +A[i])%mod;
        hashA2=(hashA2*base +A[i])%mod2;

        if(i!=0)
        {
            Mx=(Mx*base)%mod;
            Mx2=(Mx2*base)%mod2;
        }
    }

    if(m>n)
    {
        printf("0\n");
        return 0;
    }

    for(int i=0; i<m; ++i)
        hash1=(hash1*base +B[i])%mod,
        hash2=(hash2*base +B[i])%mod2;

    int Nr=0;

    for(int i=0; i<=n-m; ++i)
    {
        if(hash1==hashA1 && hash2==hashA2)
            match[i]=1, ++Nr;
        hash1=( (hash1 - (B[i]*Mx) %mod  +mod ) * base +B[i+m] ) %mod;
        hash2=( (hash2 - (B[i]*Mx2)%mod2 +mod2) * base +B[i+m] ) %mod2;
    }

    printf("%d\n",Nr);

    Nr=0;
    for(int i=0; i<n && Nr<=1000; ++i)
        if(match[i]==1)
            ++Nr,
            printf("%d ",i);

    fclose(stdin); fclose(stdout);
    return 0;
}