Cod sursa(job #2288910)

Utilizator danin01Nastase Daniel danin01 Data 24 noiembrie 2018 09:26:34
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <string.h>
#include <stdio.h>
using namespace std;

FILE*f=fopen("strmatch.in","r");
FILE*g = fopen("strmatch.out","w");

char A[2000001],B[2000001];

int k=0,poz[1001],nrpoz,nr;

int P[2000001];

int main()
{
    fscanf(f,"%s",A+1);
    fscanf(f,"%s",B+1);

    for(int i=2;i<=strlen(A+1);++i)
    {

        for(;k!=0 && A[k+1]!=A[i];)k=P[k];
        if(A[k+1]==A[i])k++;
        P[i]=k;

    }

    for(int i=1;i<=strlen(B+1);++i)
    {

       for(;k!=0 && A[k+1]!=B[i];)k=P[k];
       if(A[k+1]==B[i])k++;
       if(k==strlen(A+1))
       {
           nr++;
           if(nrpoz<=999)
           {
               nrpoz++;
               poz[nrpoz]=i-strlen(A+1);
           }
       }

    }

    fprintf(g,"%d\n",nr);

    for(int i=1;i<=nrpoz;++i)
    {
        fprintf(g,"%d ",poz[i]);
    }

    return 0;
}