Cod sursa(job #1518232)

Utilizator maria.nastaseNastase Maria maria.nastase Data 5 noiembrie 2015 19:21:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define m1 100007
#define m2 100021
#define baza 123

char s1[2000001],s2[2000001];
int sol[1001];
int main()
{
    int s1_1=0, s1_2=0, s2_1=0, s2_2=0;
    int k1,k2;
    int p1=1, p2=1;
    int nr_sir=0;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s%s",s1,s2);
    k1=strlen(s1);
    k2=strlen(s2);
    if(k1>k2)
        printf("0");
    else
    {
        for(int i=0; i<k1; i++)
        {
            s1_1=(s1_1*baza+s1[i])%m1;
            s1_2=(s1_2*baza+s1[i])%m2;
            if(i>=1)
            {
                p1=(p1*baza)%m1;
                p2=(p2*baza)%m2;
            }
        }
        for(int i=0; i<k1; i++)
        {
            s2_1=(s2_1*baza+s2[i])%m1;
            s2_2=(s2_2*baza+s2[i])%m2;
        }
        if(s1_1==s2_1 && s1_2==s2_2)
        {
            nr_sir++;
            sol[nr_sir]=0;
        }
        for(int i=k1; i<k2; i++)
        {
            s2_1=(((s2_1-(s2[i-k1]*p1)%m1+m1)%m1)*baza+s2[i])%m1;
            s2_2=(((s2_2-(s2[i-k1]*p2)%m2+m2)%m2)*baza+s2[i])%m2;
            if(s1_1==s2_1 && s1_2==s2_2)
            {
                nr_sir++;
                if(nr_sir<=1000)
                    sol[nr_sir]=i-k1+1;
            }
        }
        printf("%d\n",nr_sir);
        if(nr_sir>1000)
            nr_sir=1000;
        for(int i=1; i<=nr_sir; i++)
            printf("%d ",sol[i]);
    }
    return 0;
}