C语言算法实现：查找字符串长度为m的所有不重复子串

题目需求分析

该问题的目标是从给定的字符串中，找出所有长度为 m 的子串，并筛选出不重复的部分，最后按照字典序排列输出。例如，对于输入字符串 "aaab" 且 m=2 时：

• 所有长度为2的子串依次为："aa", "aa", "ab"。
• 去重后的唯一子串为："aa", "ab"。

算法逻辑与步骤

第1步：读取输入数据

首先需要读取样例数量 K，并在每个样例中读取目标子串长度 m 和原始字符串 str。由于字符串仅由小写字母组成且长度不超过100，可以使用固定大小的字符数组进行处理。

第2步：截取所有长度为m的子串

定义一个二维字符数组 a[102][101] 用于临时存放截取出的子串。利用双重循环：

• 外层循环控制起始位置，从索引 0 遍历至 len - m（len 为原字符串长度）。
• 内层循环负责将原字符串中连续 m 个字符复制到二维数组的当前行中。

第3步：按字典序排序

为了便于后续去重，需要对存储的子串数组进行排序。此处采用简单的冒泡排序算法，根据字符串比较结果 strcmp 交换相邻行的位置，确保数组按字典序升序排列。

第4步：去重并输出

遍历已排序的数组，利用 strcmp(a[i], a[i+1]) == 0 判断当前子串是否与下一个子串完全相同。如果不同（或为最后一个子串），则逐个字符打印；若相同则跳过。每个样例结束后需额外输出一个空行。

完整代码实现

#include <stdio.h>
#include <string.h>
 
int main() 
{
    int k, i, j, len, n, l, m;
    // a数组用于存放截取的所有子串，最大支持约100个长度为100的子串
    char str[105] = {0}, a[102][101] = {0}, temp[100];
    
    scanf("%d", &k);
    while (k--)
    {
        n = 0;
        scanf("%d", &m);
        scanf("%s", str);
        len = strlen(str);
        
        // 1. 截取子串
        for (i = 0; i <= len - m; i++)
        {
            l = 0;
            for (j = i; j < i + m; j++, l++)
            {                
                a[n][l] = str[j]; // 将子串存入二维数组
            }
            a[n][l] = '\0'; // 确保字符串结束符正确设置，防止内存残留影响排序
            n++;
        }
        
        // 2. 冒泡排序
        for (i = 0; i < n; i++)
        {
            for (j = i + 1; j < n; j++)
            {
                if (strcmp(a[i], a[j]) > 0)
                {
                    strcpy(temp, a[i]);
                    strcpy(a[i], a[j]);
                    strcpy(a[j], temp);
                }
            }
        }
        
        // 3. 去重输出
        for (i = 0; i < n; i++)
        {
            if (strcmp(a[i], a[i+1]) == 0) // 如果当前与下一个相同，则跳过
                continue;
            for (j = 0; j < m; j++)
                printf("%c", a[i][j]);
            printf("\n");
        }
        printf("\n");  
        
        // 4. 清理缓存
        memset(str, '\0', sizeof(str));  
        memset(a, '\0', sizeof(a));
        memset(temp, '\0', sizeof(temp));
    }
    return 0;
}

注意事项与排错

在原始代码基础上，建议在每次截取子串后手动添加字符串结束符 '\0'，即在执行 a[n][l] = str[j] 的内层循环结束后添加 a[n][l] = '\0'。虽然 memset 初始化保证了清零，但显式声明结束符能更有效地防止 strcmp 或 strcpy 越界读取内存，增强程序的健壮性。

以上就是C语言中如何查找并输出唯一子串的详细内容，更多关于字符串处理与去重算法的资料请关注本站其它相关文章！