Cod sursa(job #2322240)

Utilizator priboiraduPriboi Radu Bogdan priboiradu Data 17 ianuarie 2019 16:43:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

char a[2000001], b[2000001];
int pi[2000001], v[1000];

int main() {
    FILE *fin, *fout;
    int n, m, i, j, c = 0;
    fin = fopen( "strmatch.in", "r" );
    fout = fopen( "strmatch.out", "w" );
    m = 0;
    do {
        b[++m] = fgetc( fin );
    } while ( b[m] != '\n' );
    m--;
    n = 0;
    do {
        a[++n] = fgetc( fin );
    } while ( a[n] != '\n' );
    n--;
    j = 0;
    for ( i = 2; i <= m; i++ ) {
        while ( j > 0 && b[i] != b[j + 1] )
            j = pi[j];
        if ( b[i] == b[j + 1] )
            j++;
        pi[i] = j;
    }
    j = 0;
    for ( i = 1; i <= n; i++ ) {
        while ( j > 0 && a[i] != b[j + 1] )
            j = pi[j];
        if ( a[i] == b[j + 1] )
            j++;
        if ( j == m ) {
            if ( c < 1000 )
                v[c] = i;
            c++;
        }
    }
    fprintf( fout, "%d\n", c );
    c = c > 1000 ? 1000 : c;
    for ( i = 0; i < c; i++ )
        fprintf( fout, "%d ", v[i] - m );
    fclose( fin );
    fclose( fout );
    return 0;
}