演算法實作筆記：有限狀態機（FSM）實現單詞計數器

問題背景

面試經典題：「統計一個由字母與空格組成的字串中有多少個單詞？」核心考點在於有限狀態機（Finite State Machine, FSM）的建模與實作能力。單詞定義為「連續非空格字元序列」，以空格或字串結尾分隔。

狀態建模

定義三個狀態：

• INIT：初始/剛跳過空格，準備識別新單詞
• IN_WORD：正在讀取單詞內部字元
• IN_SPACE：正在讀取分隔空格

狀態轉移表

遇到 \0 直接返回計數。

C 語言實作

#include 
#include 

typedef enum { INIT, IN_WORD, IN_SPACE } State;

int count_words(const char *str) {
    if (!str) return 0;

    State state = INIT;
    int count = 0;

    while (*str) {
        char ch = *str++;
        switch (state) {
            case INIT:
                if (ch != ' ') {
                    ++count;
                    state = IN_WORD;
                } else {
                    state = IN_SPACE;
                }
                break;

            case IN_WORD:
                if (ch == ' ') state = IN_SPACE;
                break;

            case IN_SPACE:
                if (ch != ' ') {
                    ++count;
                    state = IN_WORD;
                }
                break;
        }
    }
    return count;
}

測試用例

void test_count_words(void) {
    assert(count_words(NULL) == 0);
    assert(count_words("") == 0);
    assert(count_words("hello") == 1);
    assert(count_words("china baby hello") == 3);
    assert(count_words("  leading spaces") == 2);
    assert(count_words("trailing spaces  ") == 2);
    assert(count_words("multiple   spaces") == 2);
    assert(count_words("single") == 1);
}

為什麼用 FSM？

• 邏輯清晰：將複雜的條件分支轉化為狀態與轉移，易於驗證完整性（無遺漏轉移）。
• 易擴展：新增「制表符、換行符、標點符號」作為分隔符，只需修改 ch == ' ' 判斷為 isspace(ch) 或查表，狀態結構完全不用動。
• 效能穩定：單次掃描 O(n)，分支預測友好，無回溯、無額外記憶體。
• 工程通用性：網路協議解析（TCP/IP 狀態機）、詞法分析器、遊戲 AI 行為樹、嵌入式協議棧皆大量使用 FSM。

進階：表驅動實作

為了進一步解耦邏輯與資料，可將轉移表提取為靜態結構體陣列：

typedef struct {
    State next_state;
    int   inc_count;   // 0 或 1
} Transition;

static const Transition table[3][2] = {
    /* INPUT: 非空格=0, 空格=1 */
    /* INIT      */ {{IN_WORD, 1}, {IN_SPACE, 0}},
    /* IN_WORD   */ {{IN_WORD, 0}, {IN_SPACE, 0}},
    /* IN_SPACE  */ {{IN_WORD, 1}, {IN_SPACE, 0}},
};

int count_words_table(const char *str) {
    if (!str) return 0;
    State state = INIT;
    int count = 0;
    while (*str) {
        int input = (*str++ == ' ') ? 1 : 0;
        const Transition *tr = &table[state][input];
        count += tr->inc_count;
        state = tr->next_state;
    }
    return count;
}

此寫法將「業務規則」完全資料化，修改規則只需改表，程式碼零修改，極利於維護與單元測試。

總結

單詞計數看似簡單，實則是「流式輸入、狀態保持、邊界處理」的縮影。掌握 FSM 建模（狀態定義 → 轉移表 → 表驅動實作）是從「寫出能跑的程式」進階到「寫出可維護、可擴展、可驗證系統」的關鍵技能。