看板SetupBBS
標 題[轉錄]在 M3 上實做 KMP-algorithm
發信站小鹿鹿 BBS (Fri Mar 18 14:05:48 2005)
轉信站ptt!ctu-reader!news.nctu!abpe.org
※ 本文轉錄自 [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/ & <
[email protected]>
--
※ Origin: 邪惡小鹿鹿 <Deer.twbbs.org> ◆ From: deer.math.nctu.edu.tw