用C语言写:【问题描述】应用Horspool算法在一个长度为n(n<=1000)的文本中,查找一个长度为m(n>=m)的模式。如果模式位于文本串中,返回模式首次出现的位置;如果模式不在文本串中,返回-1。文本字符集为ASCII码。 【输入形式】第一行为文本串;第二行为模式串 【输出形式】第一行为文本串;第二行为模式串;第三行开始依次为模式串中第1个到第m-1个字符c及其对应的移动距离T(c)值;倒数第二行为字符集中其他字符的移动距离;最后一行为模式首次出现的位置。
时间: 2024-03-24 17:41:23 浏览: 84
Horspool扩展算法及其在方块苗文模式匹配中的应用
好的,以下是使用 C 语言实现 Horspool 算法的代码:
```c
#include <stdio.h>
#include <string.h>
#define MAX_N 1000
#define MAX_M 1000
#define MAX_CHAR 256
int horspool(char *text, char *pattern, int n, int m)
{
if (n < m)
return -1;
// 计算坏字符表
int bc[MAX_CHAR];
for (int i = 0; i < MAX_CHAR; i++)
bc[i] = m;
for (int i = 0; i < m - 1; i++)
bc[(int)pattern[i]] = m - i - 1;
// 开始匹配
int i = m - 1;
while (i < n)
{
int k = i;
int j = m - 1;
while (j >= 0 && text[k] == pattern[j])
{
k--;
j--;
}
if (j == -1)
return k + 1;
i += bc[(int)text[i]];
}
return -1;
}
int main(void)
{
char text[MAX_N + 1], pattern[MAX_M + 1];
fgets(text, MAX_N + 1, stdin);
fgets(pattern, MAX_M + 1, stdin);
int n = strlen(text) - 1;
int m = strlen(pattern) - 1;
// 删除末尾的换行符
if (text[n - 1] == '\r' || text[n - 1] == '\n')
n--;
if (pattern[m - 1] == '\r' || pattern[m - 1] == '\n')
m--;
// 打印文本串和模式串
printf("Text: %s\n", text);
printf("Pattern: %s\n", pattern);
// 计算并打印坏字符表
int bc[MAX_CHAR];
for (int i = 0; i < MAX_CHAR; i++)
bc[i] = m;
for (int i = 0; i < m - 1; i++)
{
bc[(int)pattern[i]] = m - i - 1;
printf("T(%c) = %d\n", pattern[i], bc[(int)pattern[i]]);
}
printf("T(other) = %d\n", m);
// 使用 Horspool 算法查找模式串
int pos = horspool(text, pattern, n, m);
// 打印结果
if (pos == -1)
printf("Pattern not found.\n");
else
printf("Pattern first appears at position %d.\n", pos);
return 0;
}
```
你可以将此代码保存为 `.c` 文件,使用 C 语言编译器进行编译,并运行可执行程序,查看输出结果。
阅读全文