Cod sursa(job #1242362)

Utilizator danny794Dan Danaila danny794 Data 14 octombrie 2014 13:01:40
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>

#define NMAX 2000001

using namespace std;

char A[NMAX], B[NMAX];
int pi[NMAX], lA, lB, count, position[1001];

int getLength(char *word)
{
  int length = 0;
  while(*word != '\0')
  {
    word++;
    length++;
  }
  return length;
}

void read()
{
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
  scanf("%s", A);
  lA = getLength(A);
  scanf("%s", B);
  lB = getLength(B);
}

void piCompute()
{
  pi[0] = 0;
  for(int i = 1; i < lA; i++)
  {
    int aux = pi[i-1];
    while(A[i] != A[aux] && aux)
      aux = pi[aux];
    if(A[i] == A[aux])
      pi[i] = aux + 1;
    else
      pi[i] = 0;
  }
}

void solve()
{
  int pos = 0, j = 0;
  for(int j = 0; j < lB; j++)
  {
    while(pos && B[j] != A[pos])
      pos = pi[pos-1];
    if(B[j] == A[pos])
      pos++;
    if(pos == lA)
    {
      if(count < 1001)
        position[count] = j - lA + 1;
      count++;
      pos = pi[pos-1];
    }
  }

  int a = count < 1001 ? count : 1000;

  printf("%d\n", count);
  for(int i = 0; i < a; i++)
    printf("%d ", position[i]);
}

int main() {
  read();
  piCompute();
  solve();
	return 0;
}