Cod sursa(job #1745966)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 22 august 2016 16:17:37
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
# include <iostream>
# include <fstream>

# include <stdio.h>
# include <stdlib.h>

# include <algorithm>

# include <vector>

# include <cstring>

using namespace std;

# define MAX_LEN 2000001

int pi[MAX_LEN];

char a[1 + MAX_LEN];
char b[1 + MAX_LEN];

int rez[1000];

int main() {
    FILE *fin = fopen( "strmatch.in", "r" ), *fout = fopen( "strmatch.out", "w" );
    int i, k, r, n, m, s;

    fgets( a + 1, MAX_LEN, fin );
    fgets( b + 1, MAX_LEN, fin );
    n = strlen( a + 1 );
    m = strlen( b + 1 );
    n -= ( a[n] == '\n' );
    m -= ( a[m] == '\n' );

    pi[0] = -1;
    k = r = s = 0;
    for ( i = 1; i <= m; i ++ ) {
        while ( k != -1 && b[i] != a[k + 1] )
            k = pi[k];

        k ++;
        pi[i] = k;

        if ( k == n ) {
            if ( s < 1000 )
                rez[s] = i - n;
            s ++;
        }
    }

    fprintf( fout, "%d\n", s );
    for ( i = 0; i < s && i < 1000; i ++ )
        fprintf( fout, "%d ", rez[i] );


    fclose( fin );
    fclose( fout );

    return 0;
}