难度:easy
题目描述:
这个题目理解起来比较简单就不做过多解释了,这里来详细描述两种解法:
暴力解法(这个思路就比较单纯了):
这里我们称haystack为主串,needle为模式串,原理非常简单,主串,模式串从左到右一个字符一个字符比较,如果出现有字符不一样的情况,我们让模式串的j跳回到0这个位置,然后右移一位,重新开始比较。
原理图如上图所示:
1)i=0 和 j=0 处出现不一样的字符 模式串右移
2)即为i=1 和 j=0开始比较又出现了不一样的字符 模式串右移一位
3)即为i=2和j=0开始比较,发现是一样的字符,i++ , j++
4)i=3 和j=1 处的字符依旧一模一样 此时模式串已经全部遍历完成
返回在主串中最开始出现模式串中“l”的索引即可。
具体解法:
提交结果:
中学我们一定都被老师告诉过,“这道题是对的,但是可能不是最优解法”
这里我们来探讨下第二种解法,非常让人头疼的KMP算法,来解这道题:
这里推荐去看
https://blog.csdn.net/f1033774377/article/details/82556438
https://blog.csdn.net/f1033774377/article/details/82556438
来详细了解KMP算法
由于主串是hello 模式串是ll 这个例子过于简单 所以我么么换一个例子
上述就是KMP详细求解过程
具体解法:
提交结果: