Cod sursa(job #2084422)

Utilizator doruliqueDoru MODRISAN dorulique Data 9 decembrie 2017 07:11:10
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <cstring>
using namespace std;

char a[2000010],b[2000010];
int pbase=32771,match[1010];

int main()
{
    FILE  *f=fopen("strmatch.in","r");
    fgets(a,2000010,f);
    fgets(b,2000010,f);
    int n=strlen(a),m=strlen(b);
    if(a[n-1]=='\n')a[--n]=0;
    if(b[m-1]=='\n')b[--m]=0;
    int i,ha=0,hb=0,p256=1;
    for(i=0;a[i];i++)
    {
        p256=p256*256%pbase;
        ha=(ha*256+a[i])%pbase;
        hb=(hb*256+b[i])%pbase;
    }
    int ok,j,nrap=0;
    for(i=0;i<=m-n;i++)
    {
        if(ha==hb)
        {
            ok=1;
            for(j=0;j<n;j++)
                if(a[j]!=b[i+j]){ok=0;break;}
            if(ok)
            {
                nrap++;
                if(nrap<=1000)match[nrap]=i;
            }
        }
        hb=(hb*256%pbase-b[i]*p256+b[i+n])%pbase;
        if(hb<0)hb+=pbase;
    }
    f=fopen("strmatch.out","w");
    fprintf(f,"%d\n",nrap);
    if(nrap>1000)nrap=1000;
    for(i=1;i<=nrap;i++)fprintf(f,"%d ",match[i]);
    return 0;
}