Cod sursa(job #1252782)

Utilizator binicBinica Nicolae binic Data 31 octombrie 2014 11:42:08
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
/*
Rabin-Karp

#include<cstdio>
#include<cstring>
using namespace std;
#define m1 100007
#define m2 100021
int n,m,i,a1,a2,k,p1,p2,b1,b2,c[2000001];
char a[2000001],b[2000001];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(a);
    gets(b);
    n=strlen(a)-1;
    m=strlen(b)-1;
    if(n>m)
    {
        printf("0");
        return 0;
    }
    for(i=0;i<=n;i++)
    {
        a1=(a1*73+a[i])%m1;
        a2=(a2*73+a[i])%m2;
    }
    p1=1;
    p2=1;
    for(i=0;i<=n;i++)
    {
        b1=(b1*73+b[i])%m1;
        b2=(b2*73+b[i])%m2;
        if(i>0)
        {
            p1=(p1*73)%m1;
            p2=(p2*73)%m2;
        }
    }
    if(a1==b1&&a2==b2)k++,c[k]=0;
    for(i=n+1;i<=m;i++)
    {
        b1=((b1-(b[i-n-1]*p1)%m1+m1)*73+b[i])%m1;
        b2=((b2-(b[i-n-1]*p2)%m2+m2)*73+b[i])%m2;
        if(a1==b1&&a2==b2)k++,c[k]=i-n;
    }
    printf("%d\n",k);
    if(k>1000)k=1000;
    for(i=1;i<=k;i++)
        printf("%d ",c[i]);
    return 0;
}*/


// KMP
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,i,j,k,q,d[2000002],p[2000002];
char x[2000002],y[2000002];
void constructie_pi()
{
    int k,i;
    k=0;
    p[1]=0;
    for(i=2;i<=n;i++)
    {
        while(k>0&&x[k+1]!=x[i])
            k=p[k];
        if(x[i]==x[k+1])k++;
        p[i]=k;
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(x+1);
    gets(y+1);
    x[0]=' ';
    y[0]=' ';
    n=strlen(x)-1;
    m=strlen(y)-1;
    constructie_pi();
    k=0;
    p[1]=0;
    for(i=1;i<=m;i++)
    {
        while(k>0&&x[k+1]!=y[i])
            k=d[k];
        if(y[i]==x[k+1])k++;
        d[i]=k;
    }
    for(i=1;i<=m;i++)
        if(d[i]==n)q++;
    printf("%d\n",q);
    q=0;
    for(i=n;i<=m;i++)
        if(d[i]==n)
        {
            printf("%d ",i-n);
            q++;
            if(q==1000)break;
        }
    return 0;
}