Új hozzászólás Aktív témák

• #787 amargo addikt Fire/SOUL/CD #784

  Új Válasz 2009-01-28 22:55:53 #787

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  amargo

  addikt

  válasz Fire/SOUL/CD #784 üzenetére

  Hi!

  #define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))
  
  void KR(char *x, int m, char *y, int n) {
  int d, hx, hy, i, j;
  
  /* Preprocessing */
  /* computes d = 2^(m-1) with
  the left-shift operator */
  for (d = i = 1; i < m; ++i)
  d = (d<<1);
  
  for (hy = hx = i = 0; i < m; ++i) {
  hx = ((hx<<1) + x[i]);
  hy = ((hy<<1) + y[i]);
  }
  
  /* Searching */
  j = 0;
  while (j <= n-m) {
  if (hx == hy && memcmp(x, y + j, m) == 0)
  OUTPUT(j);
  hy = REHASH(y[j], y[j + m], hy);
  ++j;
  }
  
  }

  Igazából viszont nem értem, mivel a linkelt oldalon ott van az algoritmus azt csak implementálni kell. De ezt én is a lentebb linkelt oldalról raktam be.

  Bár gondolom rothkrisz nem hiszem, hogy ennyire optimalizált kódot szeretne megírni, ha ilyet akarna, akkor ismerne még pár szóban forgót: Knuth-Morris-Pratt, Quick-Search stb...

  Implementációk

  Az én javaslatom inkább egy sima Brute force lenne, annak megvalósítás íme:

  void BF(char *x, int m, char *y, int n)
  {
  int i, j;
  /* Searching */
  for (j = 0; j <= n - m; ++j) {
  for (i = 0; i < m && x[i] == y[i + j]; ++i);
  if (i >= m)
  OUTPUT(j);
  }
  }

Új hozzászólás Aktív témák