使用c++实现应用Horspool算法在一个长度为n(n<=1000)的文本中,查找一个长度为m(n>=m)的模式。如果模式位于文本串中,返回模式首次出现的位置;如果模式不在文本串中,返回-1。文本字符集为ASCII码。
时间: 2024-02-28 12:56:21 浏览: 130
C++ 的算法
可以参考以下代码实现:
```c++
#include <iostream>
#include <cstring>
#define MAX_LEN 1005
#define ASCII_SIZE 256
using namespace std;
int Horspool(char text[], char pattern[], int n, int m);
int main() {
char text[MAX_LEN], pattern[MAX_LEN];
cin >> text >> pattern;
int n = strlen(text), m = strlen(pattern);
int pos = Horspool(text, pattern, n, m);
cout << pos << endl;
return 0;
}
int Horspool(char text[], char pattern[], int n, int m) {
int table[ASCII_SIZE];
// 构建坏字符表
for (int i = 0; i < ASCII_SIZE; i++) {
table[i] = m;
}
for (int i = 0; i < m - 1; i++) {
table[pattern[i]] = m - i - 1;
}
// 在文本串中查找模式串
int i = m - 1;
while (i < n) {
int j = m - 1;
while (text[i] == pattern[j]) {
if (j == 0) {
return i;
}
i--;
j--;
}
i += table[text[i]];
}
return -1;
}
```
这段代码中,我们首先构建了坏字符表,然后在文本串中查找模式串。如果模式串存在于文本串中,我们就返回模式串首次出现的位置;否则,返回-1。您可以将这段代码复制到您的C++开发环境中进行编译和运行,也可以根据自己的需要进行改进和调整。
阅读全文