(1)给定两个字符串 S 和 T,利用 BF 算法,在主串 S 中查找子串 T,并输出查找结果,输出时 需以文字形式对查找结果进行定性说明; (2)要求以 C++/C/Java 等编程语言进行实现; (3)建立算法时间复杂度分析模型,并利用计算机统计该算法的执行效率。用c++完成
时间: 2023-06-27 21:05:11 浏览: 157
BF算法查找字符串中字符
下面是C++代码实现BF算法查找子串T在主串S中的位置:
```
#include <iostream>
#include <string>
using namespace std;
int BF(string S, string T) {
int i = 0, j = 0;
int lenS = S.length(), lenT = T.length();
while (i < lenS && j < lenT) {
if (S[i] == T[j]) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
if (j == lenT) {
return i - j;
} else {
return -1;
}
}
int main() {
string S = "hello world";
string T = "world";
int pos = BF(S, T);
if (pos == -1) {
cout << "未找到子串T" << endl;
} else {
cout << "子串T在主串S中的位置为" << pos << endl;
}
return 0;
}
```
时间复杂度分析:
最坏情况下,需要比较的次数为 $(n-m+1)m$,其中 $n$ 为主串长度,$m$ 为子串长度。因此,BF算法的时间复杂度为 $O(nm)$。
执行效率统计:
可以使用计时函数进行统计,计算出程序执行的时间,从而得到算法的执行效率。如下所示:
```
#include <iostream>
#include <string>
#include <ctime> //计时函数头文件
using namespace std;
int BF(string S, string T) {
int i = 0, j = 0;
int lenS = S.length(), lenT = T.length();
while (i < lenS && j < lenT) {
if (S[i] == T[j]) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
if (j == lenT) {
return i - j;
} else {
return -1;
}
}
int main() {
string S = "hello world";
string T = "world";
int pos;
clock_t start, stop;
start = clock(); //开始计时
pos = BF(S, T);
stop = clock(); //停止计时
if (pos == -1) {
cout << "未找到子串T" << endl;
} else {
cout << "子串T在主串S中的位置为" << pos << endl;
}
cout << "执行时间为" << double(stop - start) * 1000 / CLOCKS_PER_SEC << "ms" << endl; //计算程序执行时间
return 0;
}
```
这里使用了 `clock()` 函数来计时,其中 `CLOCKS_PER_SEC` 表示每秒钟的计时周期数。执行效率可以根据具体的硬件环境和测试数据进行统计。
阅读全文