Cod sursa(job #645487)

Utilizator tak3rStefan Mirea tak3r Data 9 decembrie 2011 20:09:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<cstdio>
#include<cstring>
#include<vector>

#define NMAX 2000001

using namespace std;

int N,M;
char A[NMAX], B[NMAX];

int* make_table( char a[], int n ){
  int i;
  int t[n];
  
  memset( t, 0, n * sizeof( int ) );
  
  for( i=1; i<n; ++i ){
    if( a[t[i-1]] == a[i] ){
      t[i] = t[i-1] + 1;
    }
  }
  
  return t;
}

void kmp(){
  int i, p;
  int pos[M], count = 0;
  int *t = make_table( A, N );
  
  for( i=0; i<M; ++i ){
    for( p=0; p<N && i+p<M && A[p] == B[i+p]; ++p ){}
    if( p >= N ){
      pos[count] = i;
      ++count;
    } else {
      i += t[p];
    }
  }
  
  printf("%d\n", count);
  for( i=0; i<count; ++i ){
    printf("%d ", pos[i]);
  }
  
}

int main(){
  
  freopen( "strmatch.in", "r", stdin );
  freopen( "strmatch.out", "w", stdout );
  
  int i;
  
  fgets( A, sizeof(A), stdin );
  fgets( B, sizeof(B), stdin );
  
  for( N=0; A[N]>='!' && A[N]<='z'; ++N ){}
  for( M=0; B[M]>='!' && B[M]<='z'; ++M ){}
  
  kmp();
  
  return 0;
  
}