Cod sursa(job #1867515)

Utilizator smatei16Matei Staicu smatei16 Data 4 februarie 2017 10:30:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <cstring>
#define mod 66029
#define mod1 10007
#define b1 101
#define b2 109
using namespace std;
char a[2000090],b[2000090];
int i,h1,h2,v1,v2,nr,c[1003],n,m,x,y,p,p1;
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n%s",&a,&b);
    m=strlen(a);
    n=strlen(b);
    if(m>n)printf("0");
    else
    {
        p=p1=1;
        for(i=0; i<strlen(a); i++)
        {
            h1=(h1*b1%mod+(int)a[i])%mod;
            h2=(h2*b2%mod1+(int)a[i])%mod1;
            v1=(v1*b1%mod+(int)b[i])%mod;
            v2=(v2*b2%mod1+(int)b[i])%mod1;
            if(i!=0)
            {
                p=(p*b1)%mod;
                p1=(p1*b2)%mod1;
            }
        }
        if(v1==h1 && v2==h2)
        {
            nr++;
            c[nr]=0;
        }
        for(i=m; i<n; i++)
        {
            x=(int)b[i-m];
            y=(int)b[i];
            v1=(((v1-(x*p))%mod+mod)%mod*b1+y)%mod;
            v2=(((v2-(x*p1))%mod1+mod1)%mod1*b2+y)%mod1;
            if(v1==h1 && v2==h2)
            {
                nr++;
                if(nr<=1000)
                    c[nr]=i-strlen(a)+1;
            }
        }

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