顺序串的存储结构定义如下: typedef struct{ char ch[maxsize+1]; int length; }SString; 使用KMP算法,写出统计输入字符串中出现A~Z的次数的代码。
时间: 2024-05-01 10:16:13 浏览: 81
数据结构-基本算法-串定长顺序存储
以下是使用KMP算法统计输入字符串中出现A~Z的次数的代码:
```
#include <stdio.h>
#include <string.h>
#define maxsize 100
typedef struct{
char ch[maxsize + 1];
int length;
}SString;
void getnext(char *p, int next[])
{
int i = 0, j = -1;
next[0] = -1;
while (i < strlen(p)) {
if (j == -1 || p[i] == p[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
int kmp(SString s, char *p)
{
int next[maxsize];
getnext(p, next);
int i = 0, j = 0, ans = 0;
while (i < s.length) {
if (j == -1 || s.ch[i] == p[j]) {
i++;
j++;
} else {
j = next[j];
}
if (j == strlen(p)) {
ans++;
j = next[j];
}
}
return ans;
}
int main()
{
SString s;
printf("请输入一个字符串:");
gets(s.ch);
s.length = strlen(s.ch);
int count[26] = {0};
for (char c = 'A'; c <= 'Z'; c++) {
char p[2] = {c, '\0'};
count[c - 'A'] = kmp(s, p);
}
for (char c = 'A'; c <= 'Z'; c++) {
printf("%c出现的次数为:%d\n", c, count[c - 'A']);
}
return 0;
}
```
这段代码可以统计输入字符串中出现A~Z的次数,首先定义一个SString类型的结构体,使用gets函数读入一个字符串,然后对于每个字母A~Z,定义一个大小为2的字符数组p,第一个元素为该字母,第二个元素为'\0'。然后调用kmp函数统计p在输入字符串中出现的次数,最终将每个字母出现的次数打印出来。
阅读全文