用C语言及KMP算法实现给定一个字符串s和两个字符c1,c2,均保证只含有小写英文字母。请求出有多少个s的子串,符合以c1开头,以c2结束,输入第一行有一个整数n,n的范围为11到10的5次方,及C1,C2,第二行有一个字符串s,长度为n,仅包含一个小写字母
时间: 2023-06-09 17:05:23 浏览: 91
kmpC语言实现 字符串匹配 算法
我明白了你的问题。根据你所描述的要求,我们可以按以下方式使用C语言和KMP算法实现给定一个字符串s和两个字符c1和c2的搜索。
首先,定义一个函数来计算KMP中的next数组:
int* getNext(char* P) {
int m = strlen(P);
int* next = malloc(sizeof(int) * m);
next[0] = -1;
int k = -1;
for (int i = 1; i < m; i++) {
while (k >= 0 && P[k+1] != P[i]) {
k = next[k];
}
if (P[k+1] == P[i]) {
k++;
}
next[i] = k;
}
return next;
}
然后,定义一个函数来计算以c1开头、以c2结束的子串数量:
int countSubstring(char* s, int len, char c1, char c2) {
int ans = 0;
char* P = malloc(sizeof(char) * (len+2));
P[0] = c1;
for (int i = 0; i < len; i++) {
P[i+1] = s[i];
}
P[len+1] = c2;
int* next = getNext(P);
int m = strlen(P);
int k = -1;
for (int i = 1; i < m-1; i++) {
while (k >= 0 && P[k+1] != P[i]) {
k = next[k];
}
if (P[k+1] == P[i]) {
k++;
}
if (k == 1) {
ans++;
}
}
free(P);
free(next);
return ans;
}
最后,将以上两个函数结合起来,实现完整的程序,如下:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int* getNext(char* P) {
int m = strlen(P);
int* next = malloc(sizeof(int) * m);
next[0] = -1;
int k = -1;
for (int i = 1; i < m; i++) {
while (k >= 0 && P[k+1] != P[i]) {
k = next[k];
}
if (P[k+1] == P[i]) {
k++;
}
next[i] = k;
}
return next;
}
int countSubstring(char* s, int len, char c1, char c2) {
int ans = 0;
char* P = malloc(sizeof(char) * (len+2));
P[0] = c1;
for (int i = 0; i < len; i++) {
P[i+1] = s[i];
}
P[len+1] = c2;
int* next = getNext(P);
int m = strlen(P);
int k = -1;
for (int i = 1; i < m-1; i++) {
while (k >= 0 && P[k+1] != P[i]) {
k = next[k];
}
if (P[k+1] == P[i]) {
k++;
}
if (k == 1) {
ans++;
}
}
free(P);
free(next);
return ans;
}
int main() {
int n;
char c1, c2, s[100000];
scanf("%d %c %c", &n, &c1, &c2);
scanf("%s", s);
printf("%d\n", countSubstring(s, n, c1, c2));
return 0;
}
__END__
以上程序实现了对字符串s中符合要求的子串进行计数,并输出计数结果。程序在输入n、c1、c2和s后执行countSubstring函数,返回符合要求的子串数量,并将结果输出。
希望我的回答能够解决你的问题。
阅读全文