轉信站: GIBBS!news2.ncku!ccnews.ncku!news.ccns.ncku!news.mksh.phc!news.nsysu!ne
Origin: deer.math.nctu.edu.tw

※ 本文轉錄自 [Daily] 看板

作者: DarkKiller (悸動) 看板: Daily
標題: 在 M3 上實做 KMP-algorithm
時間: Fri Mar 18 13:55:38 2005

在 string matching 的演算法有幾個比較有效率的方法 O(pat + str)，其中之
一是 KMP algorithm。

關於為什麼要用 KMP algorithm 以及 KMP algorithm 的演算法，請參考 DS 或
Algorithm 書籍。

在 M3 上面實做不難，只要修改一些東西就可以用。

修改 src/lib/Makefile，增加 str_str_kmp.c 及 str_str_kmp.o，然後把下列
程式碼放入 src/lib/str_str_kmp.c：

/* a alternative str_str() using KMP algorithm. */

#include <stdlib.h>

#define fast_tolower(c) (((c) >= 'A' && (c) <= 'Z') ? ((c) - 'A' + 'a') : (c))

void
str_str_kmp_tbl(pat, tbl)
  const char const *pat;
  int *tbl;
{
  register char c;
  register int i, j;

  tbl[0] = -1;
  for (j = 1; (c = pat[j]) != '\0'; j++)
  {
    i = tbl[j - 1];
    while (i >= 0 && fast_tolower(c) != fast_tolower(pat[i + 1]))
      i = tbl[i];
    if (fast_tolower(c) == fast_tolower(pat[i + 1]))
      tbl[j] = i + 1;
    else
      tbl[j] = -1;
  }
}

const char *
str_str_kmp(str, pat, tbl)
  const char const *str;
  const char const *pat;
  const int const *tbl;
{
  register char const *i;
  register int j;

  for (i = str, j = 0; *i != '\0' && pat[j] != '\0';)
  {
    if (fast_tolower(*i) == fast_tolower(pat[j]))
    {
      i++;
      j++;
    }
    else if (j == 0)
      i++;
    else
      j = tbl[j - 1] + 1;
  }

  /* match */
  if (pat[j] == '\0')
    return (i - j);

  return NULL;
}

--
                                                Resistance is futile.
                                http://gslin.org/ & <gslin@gslin.org>
--
※ Origin: 邪惡小鹿鹿 <Deer.twbbs.org> ◆ From: deer.math.nctu.edu.tw