[轉錄]Re: 在 M3 上實做 KMP-algorithm
※ 本文轉錄自 [Daily] 看板
作者: DarkKiller (悸動) 看板: Daily
標題: Re: 在 M3 上實做 KMP-algorithm
時間: Fri Mar 18 14:04:20 2005
※ 引述《DarkKiller (悸動)》之銘言：
> 在 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. */
再來是將某些使用 str_str() 的程式碼改用 str_str_kmp_tbl() +
str_str_kmp()。
要讓 KMP algorithm 有效率，選擇 pattern 掃過一次以後會比對許多 string
的程式碼會比較有用。
如 src/maple/board.c 的 class_search()：
if (pos)
{
BRD *bcache, *brd;
! int tbl[sizeof(buf) / sizeof(char) + 1];
short *chp, chn;
bcache = bshm->bcache;
str_lower(ptr, ptr);
! str_str_kmp_tbl(ptr, tbl);
pos = num = xo->pos;
max = xo->max;
chp = (short *) xo->xyz;
do
{
if (++pos >= max)
pos = 0;
chn = chp[pos];
if (chn >= 0)
{
brd = bcache + chn;
! if (str_str_kmp(brd->brdname, ptr, tbl) || str_str_kmp(brd->title, ptr, tbl))
return pos + XO_MOVE;
}
} while (pos != num);
}
以及 src/maple/post.c 的 XoXpost()：
! int filter_author, tbl[sizeof(buf) / sizeof(char) + 1];
if ((max = xo->max) <= 0) /* Thor.980911: 註解: 以防萬一 */
return XO_FOOT;
/* input condition */
key = xypostKeyword;
vget(b_lines, 0, MSG_XYPOST, key, sizeof(xypostKeyword), GCARRY);
str_lower(buf, key);
key = buf;
! str_str_kmp_tbl(key, tbl);
if (filter_author = vget(b_lines, 0, "[串接模式]作者：", author, 30, DOECHO))
{
:
:
:
/* Thor.981109: 特別注意, author是從頭match, 不是substr match, 為降低load */
if (filter_author && str_ncmp(head->owner, author, filter_author))
continue;
/* check condition */
title = str_ttl(head->title); /* gslin.021023: 先把 Re: 除外 */
! if (*key && !str_str_kmp(title, key, tbl))
continue;
sum++;
/* check if in table, binary check */
及 src/maple/talk.c 的 pal_list()：
case 'f':
usr_fpath(fpath, cuser.userid, FN_PAL);
if ((fd = open(fpath, O_RDONLY)) >= 0)
{
PAL *pal;
char *userid;
int tbl[256];
mgets(-1);
! str_str_kmp_tbl(buf, tbl);
while (pal = mread(fd, sizeof(PAL)))
{
userid = pal->userid;
if (!ll_has(userid) && (pal->userno != cuser.userno) &&
!(pal->ftype & PAL_BAD) &&
! (!userno || str_str_kmp(pal->ship, buf, tbl)))
{
ll_add(userid);
reciper++;
}
}
close(fd);
}
ll_out(3, 0, MSG_CC);
userno = 0;
break;
及 src/maple/talk.c 的 ulist_search()：
if (vget(b_lines, 0, msg_uid, buf, IDLEN + 1, GCARRY))
{
char bufl[IDLEN + 1];
! int buflen, tbl[sizeof(bufl) / sizeof(char) + 1];
str_lower(bufl, buf);
buflen = strlen(bufl); /* Thor: 必定大於0 */
! str_str_kmp_tbl(bufl, tbl);
pos = num = xo->pos;
max = xo->max;
pp = ulist_pool;
do
{
pos += step;
if (pos < 0) /* Thor.990124: 假設 max 不為0 */
pos = max - 1;
else if (pos >= max)
pos = 0;
/* Thor.990124: id 則從頭 match */
/* if (str_ncmp(pp[pos]->userid, bufl, buflen)==0 */
! if (str_str_kmp(pp[pos]->userid, bufl, tbl) /* lkchu.990127: 找部份 id 好像比較好用 :p */
! || str_str_kmp(pp[pos]->username, bufl, tbl)) /* Thor.990124: 可以找 部分 nickname */
{
及 src/maple/xover.c 的 xo_thread()：
int tbl[256];
if (op & RS_CURRENT)
{
query = currtitle;
! str_str_kmp_tbl(query, tbl);
if (op & RS_FIRST)
{
if (!strcmp(query, tag)) /* 目前的就是第一筆了 */
return XO_NONE;
near = -1;
}
}
else
{
title = str_ttl(tag);
if (op & RS_FIRST)
{
if (title == tag)
return XO_NONE;
near = -1;
}
strlcpy(query = buf, title, sizeof(buf));
! str_str_kmp_tbl(query, tbl);
}
:
:
:
snprintf(query = buf, sizeof(buf), "搜尋%s(%s)：", title, (step > 0) ? "↓" : "↑");
if (!vget(b_lines, 0, query, tag, len, GCARRY))
return XO_FOOT;
/* Thor.980911: 要注意, 如果沒找到, "搜尋"的訊息會被清,
如果找到了, 則沒被清, 因傳回值為match, 沒法帶 XO_FOOT */
str_lower(query, tag);
! str_str_kmp_tbl(query, tbl);
}
:
:
:
if (((op & RS_RELATED) && !strncmp(tag, query, 40)) ||
! (!(op & RS_RELATED) && str_str_kmp(tag, query, tbl)))
{
if (op & RS_FIRST)
{
if (tag != title)
{
near = pos; /* 記下最接近起點的位置 */
neartop = top;
continue;
}
}
--
Resistance is futile.
http://gslin.org/ & <gslin@gslin.org>
--
※ Origin: 邪惡小鹿鹿 <Deer.twbbs.org> ◆ From: deer.math.nctu.edu.tw
討論串 (同標題文章)