C语言如何在字符串中查找重复的子串？

在 C 语言中，可以使用暴力枚举和 KMP 算法来查找重复的子串。

暴力枚举的思路是对于每一个子串，都在原字符串中查找是否有相同的子串。时间复杂度为 O(n^3)。

KMP 算法则是通过预处理模式串，以达到在匹配过程中可以跳过一些不必要的比较，从而提高匹配效率。时间复杂度为 O(n+m)，其中 n 和 m 分别是原字符串和模式串的长度。具体实现可以参考网上的 KMP 算法实现代码。

需要注意的是，在查找重复的子串时，需要先确定子串的长度范围。可以根据实际情况来确定，比如可以从长度为 2 开始，一直到原字符串的一半。

相关问题

如何在字符串中查找重复的子串 用C语言编写

可以使用暴力枚举的方式来查找重复的子串，具体步骤如下：

1. 从字符串开头开始枚举每一个子串。
2. 对于每一个子串，将其与后面的所有子串进行比较，查看是否有相同的子串。
3. 如果找到相同的子串，则输出该子串，并记录其出现的位置。

以下是用C语言实现的代码示例：

#include <stdio.h>
#include <string.h>

void findRepeatedSubstring(char *str) {
    int len = strlen(str);
    int i, j, k;
    int maxLen = 0, maxStart = 0;

    for (i = 0; i < len; i++) {
        for (j = i + 1; j < len; j++) {
            for (k = 0; k < len - j; k++) {
                if (str[i+k] != str[j+k]) {
                    break;
                }
            }
            if (k > maxLen) {
                maxLen = k;
                maxStart = i;
            }
        }
    }

    if (maxLen > 0) {
        printf("Repeated substring: ");
        for (i = 0; i < maxLen; i++) {
            printf("%c", str[maxStart+i]);
        }
        printf("\n");
    } else {
        printf("No repeated substring found.\n");
    }
}

int main() {
    char str[100];
    printf("Enter a string: ");
    scanf("%s", str);
    findRepeatedSubstring(str);
    return 0;
}

该程序首先读取一个字符串，并调用 `findRepeatedSubstring()` 函数来查找重复的子串。该函数通过三重循环来枚举每一个子串，并将其与后面的所有子串进行比较，找到最长的相同子串并输出。如果没有找到重复的子串，则输出相应的提示信息。

c语言提取字符串中的子串

在C语言中提取字符串中的子串通常可以使用字符串库函数 `strstr()` 或者手动实现子串查找算法。

1. 使用 `strstr()` 函数

`strstr()` 函数可以在一个字符串中查找另一个子字符串出现的位置。它的原型如下：

char *strstr(const char *str1, const char *str2);

其中，`str1` 是要查找的字符串，`str2` 是要查找的子字符串。如果 `str2` 存在于 `str1` 中，则返回 `str2` 在 `str1` 中第一次出现的地址；否则返回 `NULL`。

示例代码：

#include <stdio.h>
#include <string.h>

int main()
{
    char str1[] = "hello world";
    char str2[] = "world";

    char *p = strstr(str1, str2);

    if (p != NULL)
    {
        printf("子串 \"%s\" 在字符串 \"%s\" 中的位置是 %d\n", str2, str1, p - str1);
    }
    else
    {
        printf("子串 \"%s\" 不在字符串 \"%s\" 中\n", str2, str1);
    }

    return 0;
}

2. 手动实现子串查找算法

手动实现子串查找算法的基本思路是：在主串中从前往后逐个字符比较，如果当前字符匹配，则比较下一个字符，否则从主串的下一个字符重新开始匹配。

示例代码：

#include <stdio.h>
#include <string.h>

int main()
{
    char str1[] = "hello world";
    char str2[] = "world";

    int len1 = strlen(str1);
    int len2 = strlen(str2);

    int i, j;

    for (i = 0; i < len1 - len2 + 1; i++)
    {
        for (j = 0; j < len2; j++)
        {
            if (str1[i + j] != str2[j])
            {
                break;
            }
        }

        if (j == len2)
        {
            printf("子串 \"%s\" 在字符串 \"%s\" 中的位置是 %d\n", str2, str1, i);
            break;
        }
    }

    if (i == len1 - len2 + 1)
    {
        printf("子串 \"%s\" 不在字符串 \"%s\" 中\n", str2, str1);
    }

    return 0;
}