C语言编程题查找子字符串5种方法

1、使用 strstr 函数

strstr 函数是 C 标准库中的一个函数，用于查找子字符串在另一个字符串中的第一次出现。

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

int main() {
    char str[] = "Hello, world!";
    char sub[] = "world";
    char *pos = strstr(str, sub);
    
    if (pos != NULL) {
        printf("Found '%s' at position %ld\n", sub, pos - str);
    } else {
        printf("Substring not found\n");
    }
    
    return 0;
}

2、手动实现子字符串查找

通过遍历主字符串，逐字符比较子字符串来查找。

#include <stdio.h>

char *find_substring(const char *str, const char *sub) {
    const char *p1 = str;
    const char *p2 = sub;
    const char *p1_adv = str;
    
    while (*++p2)
        p1_adv++;
    
    while (*p1_adv) {
        char *p1_begin = (char *)p1;
        p2 = sub;
        
        while (*p1 && *p2 && *p1 == *p2) {
            p1++;
            p2++;
        }
        
        if (!*p2)
            return p1_begin;
        
        p1 = p1_begin + 1;
        p1_adv++;
    }
    
    return NULL;
}

int main() {
    char str[] = "Hello, world!";
    char sub[] = "world";
    char *pos = find_substring(str, sub);
    
    if (pos != NULL) {
        printf("Found '%s' at position %ld\n", sub, pos - str);
    } else {
        printf("Substring not found\n");
    }
    
    return 0;
}

3、使用 strcasestr 函数

strcasestr 是 GNU C 库中的一个函数，与 strstr 类似，但忽略大小写。

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

int main() {
    char str[] = "Hello, World!";
    char sub[] = "world";
    char *pos = strcasestr(str, sub);
    
    if (pos != NULL) {
        printf("Found '%s' at position %ld\n", sub, pos - str);
    } else {
        printf("Substring not found\n");
    }
    
    return 0;
}

4、使用 KMP 算法

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，预处理模式字符串以加快匹配速度。

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

void computeLPSArray(const char *pat, int M, int *lps) {
    int len = 0;
    int i = 1;
    lps[0] = 0;
    
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int KMP(const char *txt, const char *pat) {
    int M = strlen(pat);
    int N = strlen(txt);
    int lps[M];
    computeLPSArray(pat, M, lps);
    int i = 0;
    int j = 0;
    
    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }
        if (j == M) {
            return i - j;
        } else if (i < N && pat[j] != txt[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    return -1;
}

int main() {
    char txt[] = "Hello, world!";
    char pat[] = "world";
    int pos = KMP(txt, pat);
    
    if (pos != -1) {
        printf("Found '%s' at position %d\n", pat, pos);
    } else {
        printf("Substring not found\n");
    }
    
    return 0;
}

5、使用 Boyer-Moore 算法

Boyer-Moore 算法是另一种高效的字符串匹配算法，适用于处理较长的文本和模式。

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

#define NO_OF_CHARS 256

void badCharHeuristic(const char *str, int size, int badchar[NO_OF_CHARS]) {
    int i;
    for (i = 0; i < NO_OF_CHARS; i++)
        badchar[i] = -1;
    for (i = 0; i < size; i++)
        badchar[(int) str[i]] = i;
}

int BoyerMoore(const char *txt, const char *pat) {
    int m = strlen(pat);
    int n = strlen(txt);
    int badchar[NO_OF_CHARS];
    badCharHeuristic(pat, m, badchar);
    int s = 0;
    
    while (s <= (n - m)) {
        int j = m - 1;
        while (j >= 0 && pat[j] == txt[s + j])
            j--;
        if (j < 0) {
            return s;
        } else {
            s += (j - badchar[(int) txt[s + j]] > 1) ? j - badchar[(int) txt[s + j]] : 1;
        }
    }
    
    return -1;
}

int main() {
    char txt[] = "Hello, world!";
    char pat[] = "world";
    int pos = BoyerMoore(txt, pat);
    
    if (pos != -1) {
        printf("Found '%s' at position %d\n", pat, pos);
    } else {
        printf("Substring not found\n");
    }
    
    return 0;
}