首页 > 编程语言 > 详细

实现 strStr() && KMP算法引入

时间:2021-05-17 00:17:29      阅读:23      评论:0      收藏:0      [点我收藏+]

题目:

  实现 strStr() 函数。

  给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回  -1 。

 

思路:

  1 暴力匹配

  2 KMP 算法

 


 

(一)暴力匹配代码 

  1 for - for

  技术分享图片

  2 for - while

  技术分享图片

 

 


 

(二)KMP算法

    核心字段: 

      模式串,不匹配,(主串,模式串)公共前后缀

      最长公共前后缀+1位(下标从一开始)  与  主串当前位进行比较

      如下图:

           最长公共前后缀为ABA

        最长公共前后缀需要小于指针前的匹配串

                      技术分享图片

       技术分享图片


 

 

 

    今天必须搞定KMP算法

 

实现 strStr() && KMP算法引入

原文:https://www.cnblogs.com/misscai/p/14771209.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!