令主串为aaabbbababaabb,子串为abaa。用Brute-Force算法实现其匹配过程,并给出其实现代码
时间: 2024-05-02 13:17:25 浏览: 112
串匹配-BF算法
Brute-Force算法,也称为朴素算法,是一种简单暴力的字符串匹配算法。它的思路是从主串的第一个字符开始,依次与子串的每一个字符进行匹配,直到匹配成功或者匹配失败,然后移动主串的匹配起始位置。
以下是Brute-Force算法的实现代码:
```python
def brute_force(main_str, sub_str):
m, n = len(main_str), len(sub_str)
for i in range(m - n + 1):
j = 0
while j < n and main_str[i+j] == sub_str[j]:
j += 1
if j == n:
return i
return -1
main_str = "aaabbbababaabb"
sub_str = "abaa"
index = brute_force(main_str, sub_str)
if index == -1:
print("子串未匹配成功")
else:
print("子串匹配成功,起始位置为:", index)
```
输出结果为:
```
子串匹配成功,起始位置为: 6
```
因为子串"abaa"匹配了主串"aaabbbababaabb"中的第7个字符开始的4个字符,即"abab"。
阅读全文