Cod sursa(job #1262293)

Utilizator GeorgianBaditaBadita Marin-Georgian GeorgianBadita Data 13 noiembrie 2014 02:48:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 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 v1, v2, p1, p2, v[Nmax];

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    int n, m, i;
    //citire
    scanf("%s%s", &x, &y);
    n = strlen(x);
    m = strlen(y);
    // daca primul sir e mai mare decat al  2-lea nu are rost sa mai cautam
    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;
        }
    }
    int h1, h2;
    h1 = h2 = 0;
        for(i = 0; i<n; i++)
        {
            h1 = (h1 * b1 + y[i])%mod1;
            h2 = (h2 * b2 + y[i])%mod2;
        }
        int nr = 0;
        if(v1 == h1 && v2 == h2)
        {
            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;
}