字串數值比較演算法：不轉型直接比大小

問題

給定兩個等長數字字串 str1、str2（長度可能超過 64 位），不使用大整數庫，如何判斷大小？

核心觀察

• 長度不同：長者大（前提無前導零）。
• 長度相同：字典序即數值序。因為 ASCII '0'~'9' 連續遞增，逐字元比較第一個不同位即可決定大小。

演算法步驟

1. 去除前導零（或確認輸入無前導零）。
2. 比較長度，長者勝出。
3. 長度相同，從索引 0 開始逐字元比較：
   if (str1[i] > str2[i]) return 1; else if (str1[i] < str2[i]) return -1;
4. 全同則回傳 0。

C++ 參考實作

int compareNumericString(const string& a, const string& b) {
    // 1. 去前導零
    size_t i = 0, j = 0;
    while (i < a.size() && a[i] == '0') ++i;
    while (j < b.size() && b[j] == '0') ++j;
    string sa = a.substr(i), sb = b.substr(j);

    // 2. 比長度
    if (sa.size() != sb.size()) return sa.size() > sb.size() ? 1 : -1;

    // 3. 逐字元比較
    for (size_t k = 0; k < sa.size(); ++k) {
        if (sa[k] != sb[k]) return sa[k] > sb[k] ? 1 : -1;
    }
    return 0;
}

複雜度分析

• 時間：O(n)，n 為字串長度。
• 空間：O(1) 額外空間（若不複製子串可原地比較）。

延伸應用

• 超大整數排序：std::sort(vec.begin(), vec.end(), compareNumericString)。
• 版本號比較（以點分隔）：先 split 再逐段套用同上邏輯。
• 資料庫字串欄位排序：ORDER BY LENGTH(col), col 同理。

掌握「等長字典序 = 數值序」這一數學性質，即可在不支援大整數的環境下高效比較任意長度數字字串。