字符串匹配 分治法c语言

字符串匹配问题可以使用分治法来解决。下面是一个使用C语言编写的字符串匹配算法，使用分治法实现。

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

// 分治法字符串匹配函数
int match(char* text, char* pattern, int n, int m) {
    // 如果模式串长度为0，直接返回匹配成功
    if (m == 0) {
        return 1;
    }
    // 如果文本串长度小于模式串长度，直接返回匹配失败
    if (n < m) {
        return 0;
    }
    // 计算中间位置，将文本串分成两段
    int mid = n / 2;
    // 比较左半部分和模式串
    int left = match(text, pattern, mid, m);
    // 比较右半部分和模式串
    int right = match(text + mid, pattern, n - mid, m);
    // 如果左半部分或右半部分匹配成功，返回匹配成功
    if (left || right) {
        return 1;
    }
    // 否则，比较中间位置的字符和模式串第一个字符
    // 如果相等，比较中间位置后面的文本串和模式串
    if (text[mid] == pattern[0]) {
        for (int i = 0; i < m; i++) {
            if (text[mid + i] != pattern[i]) {
                return 0;
            }
        }
        return 1;
    }
    // 如果中间位置的字符和模式串第一个字符不相等，返回匹配失败
    return 0;
}

int main() {
    char text[] = "hello, world!";
    char pattern[] = "world";
    int n = strlen(text);
    int m = strlen(pattern);
    int result = match(text, pattern, n, m);
    if (result) {
        printf("匹配成功\n");
    } else {
        printf("匹配失败\n");
    }
    return 0;
}

该算法的时间复杂度为O(nlogn)，其中n为文本串长度。由于使用了递归，空间复杂度为O(logn)。