c的kmp_index
时间: 2024-03-20 19:41:48 浏览: 39
以下是 C 语言中 KMP 算法的字符串匹配实现,返回匹字符串的起始下标:
```c
#include <stdio.h>
#include <string.h>
void getNext(char* pattern, int* next) {
int n = strlen(pattern);
next[0] = -1;
int j = -1;
for (int i = 1; i < n; i++) {
while (j >= 0 && pattern[i] != pattern[j + 1]) {
j = next[j];
}
if (pattern[i] == pattern[j + 1]) {
j++;
}
next[i] = j;
}
}
int kmpIndex(char* text, char* pattern) {
int next[strlen(pattern)];
getNext(pattern, next);
int n = strlen(text), m = strlen(pattern);
int j = -1;
for (int i = 0; i < n; i++) {
while (j >= 0 && text[i] != pattern[j + 1]) {
j = next[j];
}
if (text[i] == pattern[j + 1]) {
j++;
}
if (j == m - 1) {
return i - j;
}
}
return -1;
}
int main() {
char text[] = "hello world!";
char pattern[] = "world";
int pos = kmpIndex(text, pattern);
if (pos != -1) {
printf("匹配成功,起始下标为:%d\n", pos);
} else {
printf("匹配失败!\n");
}
return 0;
}
```
其中 getNext 函数是求出模式串 pattern 的 next 数组,kmpIndex 函数是实现 KMP 算法的字符串匹配过程。