Cod sursa(job #645493)

Utilizator tak3rStefan Mirea tak3r Data 9 decembrie 2011 20:15:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 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' && A[N] <= 'Z') || (A[N] >= 'a' && A[N] <= 'z') || (A[N] >= '0' && A[N] <= '9'); ++N);
  for (M=0; (B[M] >= 'A' && B[M] <= 'Z') || (B[M] >= 'a' && B[M] <= 'z') || (B[M] >= '0' && B[M] <= '9'); ++M);
  
//  for( N=0; A[N]>='!' && A[N]<='z'; ++N ){}
//  for( M=0; B[M]>='!' && B[M]<='z'; ++M ){}
  
  kmp();
  
  return 0;
  
}