Cod sursa(job #1300833)

Utilizator thinkphpAdrian Statescu thinkphp Data 24 decembrie 2014 23:31:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define MAX 2000007
#define MAX_MATCHES 1000

using namespace std;

char A[ MAX ],
     B[ MAX ];

int N,
    M;

vector<int> sol;

int Prefix[ MAX ];

int min(int a, int b) {

    return (a < b) ? a : b; 
};

void BuildPrefix() {

     int p = 0;

     Prefix[ 1 ] = 0; 

     for(int i = 2; i <= N; i++) {

         while( p > 0 && A[ p + 1] != A[ i ] ) {

                p = Prefix[ p ];
         } 

         if( A[ p + 1 ] == A[ i ] ) p++;

         Prefix[ i ] = p; 
     }  
};

void Matches() {

     int p = 0;

     for(int i = 1; i <= M; i++) {

         while( p > 0 && A[ p + 1 ] != B[ i ] ) {

                p = Prefix[ p ];
         } 

         if( A[ p + 1 ] == B[ i ] ) p++;

         if(p == N) {

             sol.push_back( i - N );

             p = Prefix[ p ];            
         }
     }  

};

void readData() {

    freopen(FIN, "r", stdin);

    scanf("%s %s", A + 1, B + 1);

    N = strlen(A + 1);
 
    M = strlen(B + 1);

    fclose( stdin );
};

void writeData() {

     freopen(FOUT, "w", stdout);

     int n = sol.size();

     printf("%d\n", n);   
 
     for(int i = 0; i < min(n, 1000); i++) {

         printf("%d ", sol[ i ]);   
     }

     fclose( stdout );
};

int main() {

    readData(); 
    BuildPrefix();
    Matches();
    writeData(); 

    return(0);
};