1.独立编写一个程序,实现字符串模式匹配BF 算法。 在Main 函数中调用自己实现BF 算法的函数,使用以下3个测 试用例进行测试: (1) 主串:abbbbccc 模式串:cc 返回值;6 (2)
时间: 2024-10-10 21:16:31 浏览: 29
串匹配-BF算法
要实现一个简单的Brute Force (暴力搜索) 字符串模式匹配算法,我们可以使用Python编写一个函数。BF算法简单地遍历主串,对于每个位置,检查其后面是否有连续的模式串出现。以下是代码实现:
```python
def bf_match(main_string, pattern):
main_len = len(main_string)
pattern_len = len(pattern)
if pattern_len > main_len:
return -1
for i in range(main_len - pattern_len + 1): # 遍历所有可能的位置
match_found = True
for j in range(pattern_len):
if main_string[i+j] != pattern[j]: # 如果当前位置的字符与模式不匹配,结束循环
match_found = False
break
if match_found: # 找到匹配,返回起始位置
return i
return -1 # 没有找到匹配
# 测试用例
test_cases = [
("abbbbccc", "cc", 6),
("hello world", "world", 6),
("abcde", "bcde", -1), # 模式过长
]
for string, pattern, expected_result in test_cases:
result = bf_match(string, pattern)
print(f"主串:{string}, 模式串:{pattern}, 返回值:{result} (期望结果:{expected_result})")
#
阅读全文