Cod sursa(job #1235237)

Utilizator george_stelianChichirim George george_stelian Data 29 septembrie 2014 02:09:28
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <cstring>

using namespace std;

const int mod1=100007,mod2=100021,p=79;
int sol[1010],n,n1,i,p1,p2,hash1,hash2,hashv1,hashv2,nr;
char v[2000010],v1[2000010];

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s\n%s",v,v1);
    n=strlen(v);
    n1=strlen(v1);
    if(n>n1)
    {
        printf("0");
        return 0;
    }
    for(i=0;i<n;i++)
    {
        hashv1=(hashv1*p+v[i]-'0')%mod1;
        hashv2=(hashv2*p+v[i]-'0')%mod2;
        hash1=(hash1*p+v1[i]-'0')%mod1;
        hash2=(hash2*p+v1[i]-'0')%mod2;
    }
    p1=p2=1;
    for(i=1;i<n;i++)
    {
        p1=(p1*p)%mod1;
        p2=(p2*p)%mod2;
    }
    if(hash1==hashv1 && hash2==hashv2) sol[++nr]=0;
    for(i=n;i<n1;i++)
    {
        hash1=(((hash1-p1*(v1[i-n]-'0')+mod1)%mod1)*p+v1[i]-'0')%mod1;
        hash2=(((hash2-p2*(v1[i-n]-'0')+mod2)%mod2)*p+v1[i]-'0')%mod2;
        if(hash1==hashv1 && hash2==hashv2) if(nr<1000) sol[++nr]=i-n+1;
                                           else nr++;
    }
    printf("%d\n",nr);
    if(nr>1000) nr=1000;
    for(i=1;i<=nr;i++) printf("%d ",sol[i]);
    return 0;
}