Category Archives: BBS

BBS

BBS, Blog, Computer, Computer and Network Center, NCTU, Network, News System, Programming, Usenet

Group.NCTU.edu.tw 對 Subject 的處理

article.php 就不說了，只講 rss10.php (原始程式碼在 http://group.nctu.edu.tw/rss10.phps)，剛剛發現 BBS 送出來的 Subject 因為會有使用 MIME-Q 的情況 (需要 patch innbbsd，或是直接用 itoc 的版本)，所以要再處理…

PS：RSS 的功能是因為讀 DS 讀到悶寫出來的，我目前沒有更多的時間發展新的功能，只能先對「正確性」處理…

BBS, Computer, KKCity, Murmuring, Network, Programming, Skysoft

BBS 的字串搜尋

2 Comments

這幾天唸 algorithm 剛好念到幾個經典的 algorithm，其中之一就是 O(m+n) 的 KMP algorithm，突然想到 BBS 應該要大量使用這類 O(m+n) 的 algorithm 才對。因為掃一次 pattern 求出 fail function 後 (當然，為了速度要存到 array) 就可以不斷的重複使用。

在 string matching (nist.gov) 有列出不少都是 O(m+n) 的演算法。(當然，O(m*n) 的暴力法一定也會列的啦)

以 M3 (Maple3) 為例，在 ‘~’ 的串接功能，以及 ‘/’ 的中文看板板名搜尋 都應該以 KMP 改寫。於是這幾天就把 KKcity 的 str_str() 換了不少下來，在看板搜尋的部分果然馬上就有感覺。(因為全 KKcity 的看板實在太多了)

應該把 str_str_kmp() 以及 str_str_kmp_fail() 丟出來，接下來 itoc 就會處理了 :p