在主串中求子串完整代码c语言
时间: 2024-06-13 20:07:49 浏览: 8
以下是利用KMP算法在主串中求子串的完整C语言代码:
```c
#include <stdio.h>
#include <string.h>
#define MAX_LEN 1000005
int next[MAX_LEN];
void getNext(char *t) {
int i = 0, j = -1;
next[0] = -1;
int len = strlen(t);
while (i < len) {
if (j == -1 || t[i] == t[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
int KMP(char *s, char *t) {
int i = 0, j = 0;
int s_len = strlen(s), t_len = strlen(t);
int ans = 0;
while (i < s_len) {
if (j == -1 || s[i] == t[j]) {
i++;
j++;
} else {
j = next[j];
}
if (j == t_len) {
ans++;
j = next[j];
}
}
return ans;
}
int main() {
char s[MAX_LEN], t[MAX_LEN];
scanf("%s%s", s, t);
getNext(t);
int ans = KMP(s, t);
printf("%d\n", ans);
return 0;
}
```