【问题描述】应用Horspool算法在一个长度为n(n<=1000)的文本中,查找一个长度为m(n>=m)的模式。如果模式位于文本串中,返回模式首次出现的位置;如果模式不在文本串中,返回-1。文本字符集为ASCII码。 【输入形式】第一行为文本串;第二行为模式串 【输出形式】第一行为文本串;第二行为模式串;第三行开始依次为模式串中第1个到第m-1个字符c及其对应的移动距离T(c)值;倒数第二行为字符集中其他字符的移动距离;最后一行为模式首次出现的位置。 【样例输入】 Apply Horspool's algorithm to search for the pattern BAOBAB in the text. Horspool's 【样例输出】 Apply Horspool's algorithm to search for the pattern BAOBAB in the text. Horspool's
时间: 2024-03-24 17:41:18 浏览: 91
字符串匹配算法之Horspool算法
以下是使用 Horspool 算法在 C 语言中实现字符串匹配的代码,可以参考一下:
```c
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 1000
#define ASCII_SIZE 128
void generateTable(int* table, char* pattern) {
int m = strlen(pattern);
for (int i = 0; i < ASCII_SIZE; i++) {
table[i] = m;
}
for (int i = 0; i < m - 1; i++) {
table[pattern[i]] = m - 1 - i;
}
}
int search(char* text, char* pattern) {
int n = strlen(text);
int m = strlen(pattern);
int table[ASCII_SIZE];
generateTable(table, pattern);
int i = m - 1;
while (i < n) {
int k = 0;
while (k < m && pattern[m - 1 - k] == text[i - k]) {
k++;
}
if (k == m) {
return i - m + 1;
}
i += table[text[i]];
}
return -1;
}
int main() {
char text[MAX_SIZE];
char pattern[MAX_SIZE];
fgets(text, MAX_SIZE, stdin);
fgets(pattern, MAX_SIZE, stdin);
int table[ASCII_SIZE];
generateTable(table, pattern);
int m = strlen(pattern);
printf("%s", text);
printf("%s", pattern);
for (int i = 0; i < m - 1; i++) {
printf("%c %d\n", pattern[i], table[pattern[i]]);
}
for (int i = 0; i < ASCII_SIZE; i++) {
if (table[i] != m) {
printf("%c %d\n", (char)i, table[i]);
}
}
int index = search(text, pattern);
printf("%d\n", index);
return 0;
}
```
输入的文本和模式串均使用 `fgets()` 函数读入,其中 `generateTable()` 函数用于生成移动表,`search()` 函数用于在文本中查找模式串,最后按照题目要求输出各个字符移动距离和模式首次出现的位置。
阅读全文