C++ 查找字符在字符串中出現次數的演算法實現

前言

在字符串處理中，統計特定字符或子字符串出現次數是常見需求。本文提供一個基於 C 風格字符串的查找函數實現，並分析其邏輯與潛在問題。

一、函數實現

int count1(char* str, char* s) {
    char* s1;
    char* s2;
    int count = 0;
    while (*str != '\0') {
        s1 = str;
        s2 = s;
        while (*s2 == *s1 && (*s2 != '\0') && (*s1 != '0')) {
            s2++;
            s1++;
        }
        if (*s2 == '\0')
            count++;
        str++;
    }
    return count;
}

二、演算法邏輯分析

1. 外層迴圈遍歷主字符串 str 的每個起始位置
2. 內層迴圈同時比較 str 從當前位置開始的子串與目標字符串 s
3. 若內層迴圈因 *s2 == '\0' 結束，表示完整匹配，計數器加一
4. 外層迴圈移動到下一個字符繼續查找

三、程式碼問題與改進

發現的問題

• 條件 *s1 != '0' 可疑：應為 *s1 != '\0' (空字符)，否則遇到字符 '0' 會誤判斷
• 重疊匹配：若搜尋 "aaa" 中的 "aa"，會計為 2 次 (位置 0 和 1)，符合一般預期
• 空字符串處理：若 s 為空字符串，會導致無限迴圈或未定義行為
• 參數 const 正確性：應宣告為 const char*

改進版本

int countSubstring(const char* str, const char* substr) {
    if (!str || !substr || *substr == '\0') return 0;
    
    int count = 0;
    const char* p = str;
    while (*p) {
        const char* s1 = p;
        const char* s2 = substr;
        while (*s2 && *s1 == *s2) {
            ++s1; ++s2;
        }
        if (*s2 == '\0') ++count;
        ++p;
    }
    return count;
}

四、現代 C++ 替代方案

使用 std::string 與 std::search

#include <string>
#include <algorithm>

int countSubstring(const std::string& str, const std::string& substr) {
    if (substr.empty()) return 0;
    int count = 0;
    auto it = str.begin();
    while ((it = std::search(it, str.end(), substr.begin(), substr.end())) != str.end()) {
        ++count;
        ++it;  // 允許重疊匹配；若不允許改為 it += substr.length()
    }
    return count;
}

使用 string::find (不重疊)

int countSubstringNoOverlap(const std::string& str, const std::string& substr) {
    if (substr.empty()) return 0;
    int count = 0;
    std::size_t pos = 0;
    while ((pos = str.find(substr, pos)) != std::string::npos) {
        ++count;
        pos += substr.length();
    }
    return count;
}

五、總結

原始函數展示了基礎指標操作邏輯，但存在邊界條件缺陷。實務開發建議使用 std::string 配合標準演算法，更安全、可讀且易維護。