Cod sursa(job #1255776)

Utilizator valexVochescu Alexandru valex Data 5 noiembrie 2014 09:22:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 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;

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

    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[0]=1;
    }

    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[i-m+1]=1;
        }
    }

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