純 C 語言英漢字典：KMP 演算法實作與原始碼分享

專案緣起

研一時出於興趣開發，核心採用 KMP（Knuth-Morris-Pratt）字串匹配演算法，查找效率 O(n+m)。若詞庫收錄則顯示中文釋義，否則提示使用者輸入新詞條——雛形的互動式字典。

核心資料結構

#define MAXSIZE 10000
typedef struct {
    char ch[MAXSIZE];
    int  length;
} Seqstr;

關鍵函式

建立 Next 陣列（部分匹配表）

void Getnext(Seqstr p, int next[]) {
    next[0] = -1;
    int i = 0, j = -1;
    while (i < p.length) {
        if (j == -1 || p.ch[i] == p.ch[j]) {
            ++i; ++j;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

KMP 搜尋主流程

void Kmp(Seqstr t, Seqstr p, int next[]) {
    int i = 0, j = 0, appearTimes = 0, lines = 1;
    while (i < t.length) {
        while (i < t.length && j < p.length) {
            if (j == -1 || t.ch[i] == p.ch[j]) { ++i; ++j; }
            else j = next[j];
            if (t.ch[i] == '\n') { lines++; i++; }
        }
        if (j == p.length) {
            printf("第 %d 次出現於第 %d 行\n", ++appearTimes, lines);
            j = 0; // 繼續尋找下一個
        }
    }
}

檔案格式範例

good 好的
hi 你好

現代化改進建議

• 動態記憶體分配取代固定 MAXSIZE
• 使用 Trie 樹或雙陣列 Trie (DAT) 替代 KMP，支援前綴搜尋與更快查找
• 詞庫採用二進制序列化格式（如 msgpack），載入速度提升數量級
• 加入發音、詞性、例句等豐富欄位

作者：鄧秀茂