C语言判断字符串是否为另一个字符串的子串

在C语言中，判断一个字符串是否为另一个字符串的子串可以通过多种方法实现。下面简要介绍两种常见的方法：暴力匹配和KMP算法。

1. 暴力匹配（Brute Force）

暴力匹配是一种简单直观的方法，它逐个字符地在主串中寻找子串的出现位置。

实现步骤：

• 遍历主串中每个可能的起始位置。
• 对于每个起始位置，逐个字符比较主串和子串中的字符。
• 如果完全匹配，返回子串在主串中的起始位置；否则，继续检查下一个位置。

示例代码：

c
复制代码
#include <stdio.h>
#include <string.h>

int isSubstring(char *mainStr, char *subStr) {
    int mainLen = strlen(mainStr);
    int subLen = strlen(subStr);
    
    for (int i = 0; i <= mainLen - subLen; ++i) {
        int j;
        for (j = 0; j < subLen; ++j) {
            if (mainStr[i + j] != subStr[j])
                break;
        }
        if (j == subLen) // 子串完全匹配
            return i;
    }
    
    return -1; // 没有找到子串
}

int main() {
    char mainStr[] = "Hello, World!";
    char subStr[] = "World";
    
    int pos = isSubstring(mainStr, subStr);
    
    if (pos != -1)
        printf("子串 \"%s\" 在主串 \"%s\" 中的位置是：%d\n", subStr, mainStr, pos);
    else
        printf("子串 \"%s\" 不是主串 \"%s\" 的子串\n", subStr, mainStr);
    
    return 0;
}

2. KMP算法

KMP算法利用了前缀函数（Partial Match Table）来优化匹配过程，能够在O(m+n)的时间复杂度内完成匹配，其中m和n分别是主串和子串的长度。

实现步骤：

• 构建子串的前缀函数（部分匹配表）。
• 利用前缀函数进行匹配，避免不必要的回溯。

示例代码：

c
复制代码
#include <stdio.h>
#include <string.h>

void computeLPSArray(char *subStr, int subLen, int *lps) {
    int len = 0; // 最长匹配前缀的长度
    lps[0] = 0; // 第一个字符的前缀长度总是0
    
    int i = 1;
    while (i < subLen) {
        if (subStr[i] == subStr[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0)
                len = lps[len - 1];
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int KMPSearch(char *mainStr, char *subStr) {
    int mainLen = strlen(mainStr);
    int subLen = strlen(subStr);
    
    int lps[subLen]; // 用于存储部分匹配表（最长匹配前缀长度）
    computeLPSArray(subStr, subLen, lps);
    
    int i = 0; // 主串索引
    int j = 0; // 子串索引
    
    while (i < mainLen) {
        if (subStr[j] == mainStr[i]) {
            j++;
            i++;
        }
        
        if (j == subLen) {
            return i - j; // 找到子串在主串中的位置
            j = lps[j - 1];
        } else if (i < mainLen && subStr[j] != mainStr[i]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }
    
    return -1; // 没有找到子串
}

int main() {
    char mainStr[] = "Hello, World!";
    char subStr[] = "World";
    
    int pos = KMPSearch(mainStr, subStr);
    
    if (pos != -1)
        printf("子串 \"%s\" 在主串 \"%s\" 中的位置是：%d\n", subStr, mainStr, pos);
    else
        printf("子串 \"%s\" 不是主串 \"%s\" 的子串\n", subStr, mainStr);
    
    return 0;
}

这两种方法各有优劣，暴力匹配简单直观但效率较低，适用于较短的字符串；而KMP算法则更适合处理较长的字符串，通过前缀函数实现了时间复杂度的优化。选择合适的方法取决于具体的应用场景和数据量大小。