Cod sursa(job #1255782)

Utilizator valexVochescu Alexandru valex Data 5 noiembrie 2014 09:36:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
//Solutie folosind Rabin-Karp
#include <cstdio>
#include <cstring>
using namespace std;
#define b1 27
#define b2 29
#define mod1 10007
#define mod2 666013

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

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

    //citire
    scanf("%s",&x);
    scanf("%s",&y);
    m=strlen(x);
    n=strlen(y);

    //daca primul sir e mai mare decat cel de-al doilea
    if (m>n)
    {
        printf("0\n");
        return 0;
    }

    p1=p2=1;
    v1=v2=0;

    for (i=0;i<m;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<m;i++)
    {
        h1=(h1*b1+y[i])%mod1;
        h2=(h2*b2+y[i])%mod2;
    }

    if (h1==v1&&h2==v2)
    {
        nr++;
        v[nr]=0;
    }

    for (i=m;i<n;i++)
    {
        h1=((h1-(y[i-m]*p1)%mod1+mod1)*b1+y[i])%mod1;
        h2=((h2-(y[i-m]*p2)%mod2+mod2)*b2+y[i])%mod2;
        if (h1==v1&&h2==v2)
        {
            nr++;
            v[nr]=i-m+1;
        }
    }

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