Cod sursa(job #1262297)

Utilizator GeorgianBaditaBadita Marin-Georgian GeorgianBadita Data 13 noiembrie 2014 03:04:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <cstring>
#define Nmax 20000001
#define b1 27
#define b2 29
#define mod1 10007
#define mod2 666013

char x[Nmax], y[Nmax];
int p1,v1,p2,v2,h1,h2, v[Nmax], nr;

int main()
{
    int n,m, i;
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s%s", &x, &y);
    n = strlen(x);
    m = strlen(y);
   // printf("%s", x);
    if(n > m)
    {
        printf("%d", 0);
        return 0;
    }
    p1=p2=1;
    for(i = 0; i<n; i++)
    {
        v1 = (v1 * b1 + x[i]) %mod1;
        v2 = (v2 * b2 + x[i]) %mod2;
        if(i >= 1)
        {
            p1 = (p1 * b1)% mod1;
            p2 = (p2 * b2)% mod2;
        }
    }
    h1 = h2 = 0;
      for(i = 0; i<n; i++)
        {
            h1 = (h1 * b1 + y[i])%mod1;
            h2 = (h2 * b2 + y[i])%mod2;
        }
    nr = 0;
    if(v1 == h1 && h2 == v2)
    {
        nr++;
        v[nr] = 0;
    }
     for(i =n; i<=m; i++)
        {
            h1=((h1-(y[i-n]*p1)%mod1+mod1)*b1+y[i])%mod1;
            h2=((h2-(y[i-n]*p2)%mod2+mod2)*b2+y[i])%mod2;
            if(h1 == v1 && v2 == h2)
            {
                nr ++;
                v[nr] = i - n + 1;
            }
        }

    printf("%d\n", nr);
    for(i =1 ;i<=nr && i<=1000; i++)
    {
        printf("%d ",v[i]);
    }
    return 0;

}