Cod sursa(job #2067684)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 16 noiembrie 2017 19:04:52
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <cstdio>
#define MOD1 100007
#define MOD2 100021
#define BAZA 73
using namespace std;
char a[2000001],b[2000001];
int ok[1001];
int verif (int inc,int n){
    int i,j=0;
    for (i=inc;i-inc+1<=n;i++,j++)
        if (a[j]!=b[i])
            return 0;
    return 1;
}
int main()
{
    FILE *fin=fopen ("strmatch.in","r");
    FILE *fout=fopen ("strmatch.out","w");
    int n,m,sol,p1,p2,i;
    int coda1,coda2,codb1,codb2;
    char c;
    c=fgetc (fin);
    n=m=-1;
    sol=0;
    while (c!='\n'){
        a[++n]=c;
        c=fgetc (fin);
    }
    c=fgetc (fin);
    while (c!='\n' && c!=EOF){
        b[++m]=c;
        c=fgetc (fin);
    }
    if (n>m){
        fprintf (fout,"0");
        return 0;
    }
    coda1=coda2=0;
    p1=p2=1;
    for (i=0;i<=n;i++){
        coda1=( coda1 * BAZA + a[i])%MOD1;
        coda2=( coda2 * BAZA + a[i])%MOD2;
        if (i!=0){
            p1=(p1*BAZA)%MOD1;
            p2=(p2*BAZA)%MOD2;
        }
    }
    codb1=codb2=0;
    for (i=0;i<=n;i++){
        codb1=(codb1*BAZA+b[i])%MOD1;
        codb2=(codb2*BAZA+b[i])%MOD2;
    }
    if (codb1==coda1 && codb2==coda2 && verif (0,n))
        ok[++sol]=0;
    for (i=n+1;i<=m;i++){
        //printf ("%d %d\n",codb1,codb2);
        codb1=( ( codb1- ( b[i-n-1]*p1 ) %MOD1 + MOD1) * BAZA + b[i]) %MOD1;
        codb2=( ( codb2- ( b[i-n-1]*p2 ) %MOD2 + MOD2) * BAZA + b[i]) %MOD2;
        if (codb1==coda1 && codb2==coda2 && verif (i-n,n))
            ok[++sol]=i-n;
    }
    fprintf (fout,"%d\n",sol);
    for (i=1;i<=sol && i<=1000;i++)
        fprintf (fout,"%d ",ok[i]);
    return 0;
}