Cod sursa(job #167291)

Utilizator vlad.maneaVlad Manea vlad.manea Data 29 martie 2008 13:56:24
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <stdio.h>
#include <string.h>
#define nmax 2000005
#define MOD 666013
#define base 27


int N, M, H0, base2, H[nmax], pot, V[1024];

char T[nmax], P[nmax];

void read()
{
  freopen("strmatch.in", "r", stdin);
  scanf("%s\n%s", &P, &T);
}

void solve()
{
  int i, j, k;

  N = strlen(T);
  M = strlen(P);

  for (i = 0; i < M; ++i)
    H0 = (H0 * base + P[i]-'A') % MOD;

  for (i = 0; i < M; ++i)
    H[M-1] = (H[M-1] * base + T[i]-'A') % MOD;

  for (base2 = 1, i = 1; i <= M; ++i)
    base2 *= base;

  for (i = M; i < N; ++i)
    H[i] = (H[i-1] * base + T[i]-'A' - base2%MOD*(T[i-M]-'A')%MOD + MOD) % MOD;

  for (i = M-1; i < N; ++i)
    if (H[i] == H0)
    {
      for (j = 0, k = i-M+1; j < M && P[j] == T[k]; ++k, ++j);
      if (j == M && pot < 1000)
          V[++pot] = k-M;
    }
}

void write()
{
  int i;

  freopen("strmatch.out", "w", stdout);

  printf("%d\n", pot);

  for (i = 1; i <= pot; ++i)
    printf("%d ", V[i]);
}

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