字符串子串統計：C語言實現所有子串頻率分析

字符串統計問題：查找出現次數最多的子串

給定一個字符串和最小長度 L，統計所有長度 ≥ L 的子串出現頻率，輸出頻率最高者（多解輸出任一）。採用暴力枚舉 + 結構體存儲 + 冒泡排序實現。

算法流程

1. 輸入最小長度 l 和目標字符串 str
2. 外層循環枚舉子串長度 l_temp 從 strlen(str) 遞減至 l
3. 中層循環枚舉起始位置 i
4. 內層提取子串並查找/插入統計數組
5. 按出現次數降序冒泡排序
6. 輸出 substr[0].sstr

核心代碼

struct sub_str {
    char sstr[61];
    int len;
    int times;
};

struct sub_str substr[1830];  // 最大子串數：60+59+...+1=1830
int sstr_num = 0;

// 枚舉所有符合長度的子串
for (l_temp = str_len; l_temp >= l; l_temp--) {
    for (i = 0; i <= str_len - l_temp; i++) {
        // 提取子串到 sstr_temp
        for (j = i, k = 0; j < i + l_temp; j++, k++)
            sstr_temp[k] = str[j];
        
        // 查找是否已存在
        for (k = 0; k < sstr_num; k++)
            if (strcmp(sstr_temp, substr[k].sstr) == 0) {
                substr[k].times++;
                break;
            }
        
        // 新子串插入
        if (k == sstr_num) {
            strcpy(substr[sstr_num].sstr, sstr_temp);
            substr[sstr_num].len = l_temp;
            substr[sstr_num].times = 1;
            sstr_num++;
        }
        memset(sstr_temp, 0, sizeof(sstr_temp));
    }
}

// 冒泡排序（按 times 降序）
for (i = 0; i < sstr_num - 1; i++)
    for (j = i; j < sstr_num; j++)
        if (substr[j].times > substr[i].times)
            swap(substr[i], substr[j]);  // 結構體整體交換

puts(substr[0].sstr);

複雜度與優化方向

• 時間複雜度：O(n³) —— n=60 時可接受，大數據量需改用後綴自動機/陣列
• 空間複雜度：O(n²)
• 優化建議：哈希表加速查找、後綴數組減少重複比較