用BF算法,结构体类型描述串的存储结构编写具体函数实现子串位置的定位函数,例如编写串的判等、求串长、求子串等操作函数实现,c语言实现
时间: 2024-05-14 17:15:14 浏览: 81
数据结构C++ 串的基本操作和BF算法与KMP算法的比较—适合初学者和复习.docx
5星 · 资源好评率100%
首先,定义结构体类型描述串的存储结构:
```c
#define MAXLEN 100
typedef struct {
char ch[MAXLEN];
int length;
} SString;
```
其中,`ch`数组存放串的字符,`length`表示串的长度。
接下来,实现串的判等函数`StrEqual`:
```c
bool StrEqual(SString s, SString t) {
if (s.length != t.length) {
return false;
}
for (int i = 0; i < s.length; i++) {
if (s.ch[i] != t.ch[i]) {
return false;
}
}
return true;
}
```
该函数首先比较两个串的长度,如果不相等则直接返回`false`;否则逐个字符比较,如果有不相等的字符则返回`false`,否则返回`true`。
接下来,实现求串长函数`StrLength`:
```c
int StrLength(SString s) {
return s.length;
}
```
直接返回串的长度即可。
接下来,实现求子串函数`SubString`:
```c
bool SubString(SString s, int pos, int len, SString& sub) {
if (pos < 1 || pos > s.length || len < 0 || len > s.length - pos + 1) {
return false;
}
for (int i = 0; i < len; i++) {
sub.ch[i] = s.ch[pos + i - 1];
}
sub.length = len;
return true;
}
```
该函数首先判断参数的合法性,如果不合法则返回`false`;否则将从`pos`开始的长度为`len`的子串复制到`sub`中,并将`sub`的长度设为`len`,最后返回`true`。
接下来,实现定位子串函数`Index`:
```c
int Index(SString s, SString t, int pos) {
int i = pos;
int j = 1;
while (i <= s.length && j <= t.length) {
if (s.ch[i - 1] == t.ch[j - 1]) {
i++;
j++;
} else {
i = i - j + 2;
j = 1;
}
}
if (j > t.length) {
return i - t.length;
} else {
return 0;
}
}
```
该函数使用了BF算法,从`pos`开始逐个字符比较`s`和`t`,如果匹配则继续比较下一个字符,否则将`i`回溯到上一个可能匹配的位置(即`i - j + 2`),将`j`重置为1,继续比较。如果`t`的所有字符都匹配,则返回匹配的起始位置,否则返回0表示匹配失败。
阅读全文