Cod sursa(job #621987)

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

int M, N;
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<=M; ++i) {
    while ((k > 0) && (A[k+1] != A[i])) 
      k = pi[k];
    if (A[k+1] == A[i])
      ++k;
    pi[i] = k;
  }
}

inline int min(int x, int y)
{
  return (x<y)?x:y;
}

int main()
{
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
  int i, q = 0, matchNo = 0;

  fgets(A, sizeof(A), stdin);
  fgets(B, sizeof(B), stdin);

  for (;(A[M]>='A' && A[M]<='Z')||(A[M]>='a' && A[M]<='z')||(A[M]>='0'&&A[M]<='9');++M);
  for (;(B[N]>='A' && B[N]<='Z')||(B[N]>='a' && B[N]<='z')||(B[N]>='0'&&B[N]<='9');++N);
	
  for (i=M; i>0; --i)
    A[i] = A[i-1];
  A[0] = ' ';
  for (i=N; i>0; --i)
    B[i] = B[i-1];
  B[0] = ' ';
	
  calcul_prefix();
	
  for (i=1; i<=N; ++i) {
    while (q && (A[q+1] != B[i]))
      q = pi[q];
    if (A[q+1] == B[i])
      ++q;
    if (q == M) {
      q = pi[M];
      ++matchNo;
      if (matchNo < 1000) 
	match[matchNo] = i-M;
    }
  }
  printf("%d\n", matchNo);
  for (i=1; i<=min(1000, matchNo); ++i)
    printf("%d ", match[i]);
  return 0;
}