数据结构c语言版 kmp

算法是什么？

KMP算法是一种字符串匹配算法，它可以在一个文本串S内查找一个模式串P的出现位置。该算法的核心思想是利用已知信息减少匹配次数，从而提高匹配效率。具体实现中，根据模式串P自身的性质，对模式串进行预处理，使得在匹配过程中可以跳过一些不必要的比较，从而快速地找到匹配位置。KMP算法的时间复杂度为O(n+m)，其中n为文本串S的长度，m为模式串P的长度。

相关问题

数据结构c语言用串实现kmp

以下是使用C语言实现KMP算法的代码，其中SString是一个自定义的串类型：

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

#define MAXSIZE 100

typedef struct {
    char ch[MAXSIZE];
    int length;
} SString;

// 获取next数组
void GetNext(SString T, int *next) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length) {
        if (j == 0 || T.ch[i - 1] == T.ch[j - 1]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

// KMP算法
int Index_KMP(SString S, SString T, int pos) {
    int i = pos, j = 1;
    int next[T.length + 1];
    GetNext(T, next);
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.ch[i - 1] == T.ch[j - 1]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j > T.length) {
        return i - T.length;
    } else {
        return 0;
    }
}

int main() {
    SString S = {"ABCABCE", 7};
    SString T = {"ABCE", 4};
    int pos = Index_KMP(S, T, 1);
    if (pos) {
        printf("匹配成功，位置为：%d\n", pos);
    } else {
        printf("匹配失败\n");
    }
    return 0;
}

用c语言实现数据结构串的KMP算法

KMP算法是一种字符串匹配算法，可以在一个主串中查找一个模式串是否出现。这里提供一个用C语言实现的KMP算法。

首先，需要定义一个函数`get_next`，用于计算模式串的next数组。next数组是一个长度为模式串长度的整型数组，表示当匹配失败时，模式串应该向右移动的位数。

void get_next(char* pattern, int* next) {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < strlen(pattern)) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        }
        else {
            j = next[j];
        }
    }
}

接下来，定义一个函数`kmp`，用于在主串中查找模式串。函数的参数包括主串指针、主串长度、模式串指针、模式串长度和next数组。

int kmp(char* text, int text_len, char* pattern, int pattern_len, int* next) {
    int i = 0, j = 0;
    while (i < text_len && j < pattern_len) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        }
        else {
            j = next[j];
        }
    }
    if (j == pattern_len) {
        return i - j;
    }
    else {
        return -1;
    }
}

下面是一个完整的示例代码：

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

void get_next(char* pattern, int* next) {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < strlen(pattern)) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        }
        else {
            j = next[j];
        }
    }
}

int kmp(char* text, int text_len, char* pattern, int pattern_len, int* next) {
    int i = 0, j = 0;
    while (i < text_len && j < pattern_len) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        }
        else {
            j = next[j];
        }
    }
    if (j == pattern_len) {
        return i - j;
    }
    else {
        return -1;
    }
}

int main() {
    char text[] = "ABABABABCABAAB";
    char pattern[] = "ABABCABAA";
    int text_len = strlen(text);
    int pattern_len = strlen(pattern);
    int next[pattern_len];
    get_next(pattern, next);
    int pos = kmp(text, text_len, pattern, pattern_len, next);
    if (pos == -1) {
        printf("Pattern not found.\n");
    }
    else {
        printf("Pattern found at position %d.\n", pos);
    }
    return 0;
}

输出结果为：

Pattern found at position 6.

表示在主串中找到了模式串，并且位置为6。