Cod sursa(job #621986)

Utilizator sebii_cSebastian Claici sebii_c Data 17 octombrie 2011 02:28:07
Problema Potrivirea sirurilor Scor 14
Compilator c Status done
Runda Arhiva educationala Marime 1.08 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;

  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=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;
    }
  }
  printf("%d\n", matchNo);
  for (i=0; i<matchNo; ++i)
    printf("%d ", match[i]);
  return 0;
}