TL;DR (太长，讲结论):
文章标题使用: DBCS_strcasestr
时间复杂度: O(n ^ 2)
※ 引述《shiburin (>\\\<)》之铭言：
: 肥宅我发现
: 如果把搜寻的字串加长
: 搜寻时间就会明显变长
: 所以ptt的搜寻是用什么算法呢
: 该不会是linear search吧
: 跑超久的
: 有没有卦？
ptt source code: https://github.com/ptt/pttbbs
追下去
|-> 有关文章的程式码:
| https://github.com/ptt/pttbbs/blob/master/mbbsd/read.c
|
|-> 有关按键按下去的触发 (Ctrl+X, r, y, ...etc):
|
| static int i_read_key(const onekey_t *rcmdlist, keeploc_t *locmem,
| int bid, int bottom_line, int pending_darws)
|
| https://github.com/ptt/pttbbs/blob/master/mbbsd/read.c#L874
|
|-> 有关 z (搜寻) 按下去的程式码:
| ...
| case '/':
| case '?':
| mode = select_read(locmem, RS_KEYWORD);
| break;
|
| case 'S:
| ...
|
| https://github.com/ptt/pttbbs/blob/master/mbbsd/read.c#L979
|
|-> 先建立出下面那排问你要搜寻啥的输入栏:
|
| static int
| ask_filter_predicate(filter_predicate_t *pred, int prev_modes, int sr_mode,
| const fileheader_t *fh, int *success)
| ...
| } else if (sr_mode & RS_KEYWORD) {
| if(!getdata(b_lines, 0,
| currmode & MODE_SELECT ? "增加条件 标题: ":"搜寻标题: ",
| keyword, TTLEN, DOECHO) || trim_blank(keyword))
| return READ_REDRAW;
|
| LOG_IF(LOG_CONF_KEYWORD, log_filef("keyword_search_log", LOG_CREAT,
| "%s:%s\n", currboard, keyword));
|
| https://github.com/ptt/pttbbs/blob/master/mbbsd/read.c#L593
|
|-> 然后再来搜寻:
|
| if (select_read_should_build(newdirect, bid, &resume_from, &count) &&
| (count = select_read_build(currdirect, newdirect, !first_select,
| force_full_build ? 0 : resume_from, count,
| match_filter_predicate, &predicate)) < 0) {
|
| https://github.com/ptt/pttbbs/blob/master/mbbsd/read.c#L855
|
|-> 如果没有被 shortcut, 就会去执行后面的 select_read_build:
|
| static int
| select_read_build(const char *src_direct, const char *dst_direct,
| int src_direct_has_reference, time4_t resume_from, int count,
| int (*match)(const fileheader_t *fh, void *arg), void *arg)
|
| 这边的 match 是个函式指标，用来搜寻用的。前面传入的是 match_filter_predicate，
| 因此可以得知是使用这个函式来搜寻。
|
| https://github.com/ptt/pttbbs/blob/master/mbbsd/read.c#L691
|
|-> 执行 match (match_filter_predicate)
|
| if (!match(&fhs[i], arg))
| continue;
|
| https://github.com/ptt/pttbbs/blob/master/mbbsd/read.c#L731
|
|-> 在 pool 中比对
|
| ...
| else if (sr_mode & RS_KEYWORD)
| return DBCS_strcasestr(fh->title, keyword) != NULL;
| ...
|
| DBCS: Double-byte Character Sets 双字节字符集。
| 这东西应该是 ptt 内部的字串编码方式。
| man strcasestr: strstr, strcasestr, strnstr