Cod sursa(job #621985)

Utilizator sebii_cSebastian Claici sebii_c Data 17 octombrie 2011 02:23:04
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX 2000005

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

void calcul_prefix() 
{
  int k = 0;
  int i;
  pi[1] = 0;
  for (i=2; i<=N; ++i) {
    while ((k > 0) && (A[k+1] != A[i])) 
      k = pi[k];
    if (A[k+1] == A[i])
      ++k;
    pi[i] = k;
  }
}

int main()
{
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
  int i, q = 0, matchNo = 0;
  scanf("%s", A); scanf("%s", B);
  N = strlen(A); M = strlen(B);
	
  for (i=N; i>0; --i)
    A[i] = A[i-1];
  A[0] = ' ';
  for (i=M; i>0; --i)
    B[i] = B[i-1];
  B[0] = ' ';
	
  calcul_prefix();
	
  for (i=1; i<=M; ++i) {
    while ((q>0) && (A[q+1] != B[i]))
      q = pi[q];
    if (A[q+1] == B[i])
      ++q;
    if (q == N) {
      match[matchNo++] = i-N+1;
    }
  }
  printf("%d\n", matchNo);
  for (i=0; i<matchNo; ++i)
    printf("%d ", match[i]-1);
  return 0;
}