Cod sursa(job #2909750)

Utilizator teodorescunicolasteodorescu nicolas alexandru teodorescunicolas Data 15 iunie 2022 12:53:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>

#define NMAXX 2000000
#define INVALID_CHAR '$'
#define MATCHMAXX 1000

using namespace std;

int z[NMAXX * 2 + 1], match[MATCHMAXX + 1];
char str[NMAXX * 2 + 1];
int strSize;


void computeZ() {
    int i, left, right;

    left = right = 0;
    for ( i = 1; i < strSize; i++ ) {
        if ( z[i - left] < right - i + 1)
            z[i] = z[i - left];
        else {
            left = i;
            if ( i > right )
                right = i;

            while ( right < strSize && str[right - left] == str[right] )
                right++;

            right--;
            z[i] = right - left + 1;
        }
    }
}


int main() {
    FILE *fin, *fout;
    int patternSize, i, nrmatch;

    fin = fopen( "strmatch.in", "r" );
    fout = fopen( "strmatch.out", "w" );

    fscanf( fin, "%s\n", str );
    patternSize = strlen( str );

    str[patternSize] = INVALID_CHAR;

    fscanf( fin, "%s", str + patternSize + 1 );
    strSize = strlen( str );

    computeZ();

    nrmatch = 0;
    for ( i = 0; i < strSize; i++ ) {
        if ( z[i] == patternSize ) {
            if ( nrmatch < MATCHMAXX )
                match[nrmatch] = i - patternSize - 1;

            nrmatch++;
        }
    }

    fprintf( fout, "%d\n", nrmatch );
    nrmatch = min( nrmatch, MATCHMAXX );
    for ( i = 0; i < nrmatch; i++ )
        fprintf( fout, "%d ", match[i] );

    fclose( fin );
    fclose( fout );
    return 0;
}