看板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