Cod sursa(job #1745953)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 22 august 2016 16:07:16
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 4.07 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];

vector<int> rez;

class ifbuffer {
    private:
        char text[100000];
        int size;
        int pos;
        bool isDigit[128];
        bool isBlank[128];

        FILE *file;

        inline void refill( void ) {
            pos = 0;
            fread( text, 1, size, file );
        }

        inline char getc() {
            char c = text[pos ++];

            if ( pos == size )
                refill();

            return c;
        }

        inline int getnr() {
            char c = getc();
            int nr = 0, p;

            while ( !isDigit[c] && c != '-' )
                c = getc();
            if ( c == '-' ) {
                p = -1;
                c = getc();
            } else
                p = 1;
            while ( isDigit[c] ) {
                nr = nr * 10 + c - '0';
                c = getc();
            }

            return nr * p;
        }

    public:
        inline ifbuffer( char * path, int s = 100000 ) {
            size = s;

            file = fopen( path, "r" );

            int i;
            for ( i = 0; i < 128; i ++ )
                isDigit[i] = isBlank[i] = false;
            for ( i = '0'; i <= '9'; i ++ )
                isDigit[i] = true;
            isBlank[' '] = isBlank['\n'] = true;

            refill();
        }

        inline ifbuffer &operator>>( int &v ) {
            v = getnr();
            return *this;
        }

        inline ifbuffer &operator>>( char &v ) {
            v = getc();
            return *this;
        }

        inline ifbuffer &operator>>( char * v ) {
            char ch;
            do {
                ch = getc();
            } while ( isBlank[ch] );
            while ( !isBlank[ch] ) {
                *(v ++) = ch;
                ch = getc();
            }

            return *this;
        }

        inline void close() {
            fclose( file );
        }
};

class ofbuffer {
    private:
        char text[100000];
        int size;
        int pos;
        bool isDigit[128];

        FILE *file;

        inline void clear( void ) {
            pos = 0;
            fwrite( text, 1, size, file );
        }

        inline void putc( char c) {
            text[pos ++] = c;

            if ( pos == size )
                clear();
        }

        inline void putnr( int nr ) {
            if ( nr < 0 ) {
                putc( '-' );
                nr =- nr;
            }

            int p10;
            for ( p10 = 1; p10 * 10LL <= nr; p10 *= 10 );
            for ( ; p10 > 0; p10 /= 10 )
                putc( nr / p10 % 10 + '0' );
        }

    public:
        inline ofbuffer( char * path, int s = 100000 ) {
            size = s;

            file = fopen( path, "w" );

            int i;
            for ( i = 0; i < '0'; i ++ )
                isDigit[i] = false;
            for ( i = '0'; i <= '9'; i ++ )
                isDigit[i] = true;
            for ( i = '9' + 1; i < 128; i ++ )
                isDigit[i] = false;
        }

        inline ofbuffer &operator<<( int v ) {
            fprintf( file, "%d", v );
            return *this;
        }

        inline ofbuffer &operator<<( char v ) {
            fputc( v, file );
            return *this;
        }

        inline void close() {
            fclose( file );
        }
};

int main() {
    ifbuffer fin( "strmatch.in" );
    ofbuffer fout( "strmatch.out" );
    int i, k, r, n, m, s;

    fin >> a + 1 >> b + 1;
    n = strlen( a + 1 );
    m = strlen( b + 1 );

    pi[0] = -1;
    k = r = 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 )
            rez.push_back( i - n );
    }

    fout << (int) rez.size() << '\n';
    s = min( (int)rez.size(), 1000 );
    for ( i = 0; i < s; i ++ )
        fout << rez[i] << ' ';


    fin.close();
    fout.close();

    return 0;
}