【问题描述】C语言实现应用Horspool算法在一个长度为n(n<=1000)的文本中,查找一个长度为m(n>=m)的模式。如果模式位于文本串中,返回模式首次出现的位置;如果模式不在文本串中,返回-1。文本字符集为ASCII码。 【输入形式】第一行为文本串;第二行为模式串 【输出形式】第一行为文本串;第二行为模式串;第三行开始依次为模式串中第1个到第m-1个字符c及其对应的移动距离T(c)值;倒数第二行为字符集中其他字符的移动距离;最后一行为模式首次出现的位置。
时间: 2024-03-24 10:39:03 浏览: 57
好的,这是一个关于Horspool算法的C语言实现问题。下面是一份代码,可以供参考:
```
#include <stdio.h>
#include <string.h>
#define MAXN 1005
#define MAXM 105
#define MAXCHAR 128
int n, m;
char text[MAXN], pattern[MAXM];
int jump[MAXCHAR]; // 记录字符集中每个字符的移动距离
void init_jump() { // 初始化 jump 数组
for (int i = 0; i < MAXCHAR; i++) {
jump[i] = m;
}
for (int i = 0; i < m - 1; i++) {
jump[pattern[i]] = m - i - 1;
}
}
int horspool() { // Horspool 算法
int i = m - 1;
while (i < n) {
int k = i;
int j = m - 1;
while (j >= 0 && text[k] == pattern[j]) {
j--;
k--;
}
if (j == -1) {
return k + 1;
}
i += jump[text[i]];
}
return -1;
}
int main() {
fgets(text, MAXN, stdin);
fgets(pattern, MAXM, stdin);
n = strlen(text) - 1; // 去掉换行符
m = strlen(pattern) - 1;
init_jump(); // 初始化 jump 数组
printf("%s%s", text, pattern);
for (int i = 0; i < m - 1; i++) {
printf("%c:%d ", pattern[i], jump[pattern[i]]);
}
printf("else:%d\n", jump['\0']);
int pos = horspool(); // 查找模式串
printf("%d\n", pos);
return 0;
}
```
该代码中,`jump` 数组记录了字符集中每个字符的移动距离,其中模式串中出现的字符移动距离为模式串中该字符最右出现位置到模式串末尾的距离,未出现的字符移动距离为模式串长度。`init_jump` 函数用于初始化 `jump` 数组。`horspool` 函数是 Horspool 算法的实现,它通过跳跃移动指针 `i` 来匹配模式串和文本串。最后,主函数输出模式串中每个字符的移动距离,以及字符集中其他字符的移动距离,最后输出模式串在文本串中首次出现的位置。
阅读全文