Cod sursa(job #613351)

Utilizator chiar_nimeninimeni chiar_nimeni Data 22 septembrie 2011 11:05:13
Problema Potrivirea sirurilor Scor 86
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cstdio>
#include <string.h>

char s1[2000005],s2[2000005];
bool ok[2000005];
int n1,n2,h1,h2,hh1,hh2,i,p1,p2,mod1,mod2,nr,p;
int main()
{
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    scanf ("%s %s", s1, s2);
    n1 = strlen (s1);
    n2 = strlen (s2);
    if (n1 > n2)
    {
        printf ("0/n");
        return 0;
    }
    p1 = p2 = 1;
    h1 = h2 = 0;
    mod1 = 100007;
    mod2 = 100021;
    p = 73;
    for (i=0; i<n1; i++)
    {
        h1 = (h1 * p + s1[i]) % mod1;
        h2 = (h2 * p + s1[i]) % mod2;
        if (i!=0)
        {
            p1 = (p1 * p) % mod1;
            p2 = (p2 * p) % mod2;
        }
    }
    hh1 = hh2 = 0;
    for (i=0; i<n1; i++)
    {
        hh1 = (hh1 * p + s2[i]) % mod1;
        hh2 = (hh2 * p + s2[i]) % mod2;
    }
    nr=0;
    if (hh1 == h1 && hh2 == h2)
    {
        ok[0] = true;
        nr++;
    }
    for (i=n1; i<n2; i++)
    {
        hh1 = ((hh1 - (s2[i-n1] * p1) % mod1 + mod1) * p + s2[i]) % mod1;
        hh2 = ((hh2 - (s2[i-n1] * p2) % mod2 + mod2) * p + s2[i]) % mod2;
        if (hh1 == h1 && hh2 == h2)
        {
            ok[i - n1 + 1] = true;
            nr++;
        }
    }
    printf ("%d\n",nr);
    nr=0;
    for (i = 0; i < n2 && nr < 1000; i++)
        if (ok[i] == true)
        {
            nr++;
            printf("%d ", i);
        }
printf("\n");
    return 0;
}