编写算法,求子串m在主串s中的位置。用主程序去调里算法,实现结果输出。
时间: 2023-11-04 22:03:07 浏览: 25
编写算法求子串m在主串s中的位置,可以使用暴力匹配算法(也称为Brute-Force算法)来实现。
算法思路如下:
1. 初始化两个指针i和j分别指向主串s和子串m的第一个字符。
2. 从主串s的第一个字符开始遍历,比较s[i]和m[j]是否相等:
- 若相等,继续比较s[i+1]和m[j+1],直到j达到子串m的末尾,表示子串m在主串s中出现;
- 若不相等,将i指针后移一位,同时将j指针重置为0,继续比较直到遍历完整个主串s。
3. 若找到了子串m在主串s中的位置,则返回子串首字符在主串中的位置;
若遍历完整个主串s,仍未找到子串m,则返回-1,表示子串m不在主串s中出现。
下面是用Python编写的示例代码:
```python
def findSubstring(s, m):
i, j = 0, 0
while i < len(s):
if s[i] == m[j]:
if j == len(m) - 1:
return i - j
i += 1
j += 1
else:
i = i - j + 1
j = 0
return -1
if __name__ == "__main__":
s = input("请输入主串s:")
m = input("请输入子串m:")
pos = findSubstring(s, m)
if pos != -1:
print("子串m在主串s中的位置为:%d" % pos)
else:
print("子串m不在主串s中出现")
```
在主程序中,通过调用findSubstring函数,并传入主串s和子串m作为参数,即可实现结果的输出。根据返回的位置pos,如果不为-1,则表示子串m在主串s中出现,输出其位置;否则,输出子串m不在主串s中出现。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)