专栏首页米扑专栏【leetcode】Implement strStr()

【leetcode】Implement strStr()

Question:

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Anwser 1:  O(n*m)

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int haylen = strlen(haystack);
        int needlen = strlen(needle);
        
        for(int i = 0; i <= haylen - needlen; i++){
            char *p = haystack + i;
            char *q = needle;
            while(*q != '\0'){
                if(*p != *q){
                    break;
                } else {
                    p++;
                    q++;
                }
            }
            
            if(*q == '\0'){
                return haystack + i;
            }
        }
        
        return NULL;
    }
};

Anwser 2:  O(n + m) KMP

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int haylen = strlen(haystack);
        int needlen = strlen(needle);
        int* fail = new int[needlen];
        memset(fail, -1, needlen * sizeof(int));    // strlen(fail)
        
        int i, j, k;
        for (i = 1; i < needlen; ++i) {
            for (k = fail[i-1]; k >= 0 && needle[i] != needle[k+1]; k = fail[k]);
            if (needle[k+1] == needle[i])
                fail[i] = k + 1;
        }
        
        i = j = 0;
      
       while(i < haylen && j < needlen)      // while(haystack[i] && needle[j])
        {
            if (haystack[i] == needle[j])
            {
                ++i;
                ++j;
            }
            else if(j == 0) ++i;
            else j = fail[j-1] + 1;
        }
        
        delete fail;
        
        /*
        if (needle[j]) {
            return NULL;
        }  else {
            return haystack + i - j;
        }*/
        if(j == needlen){
            return haystack + i - j;
        } else {
            return NULL;
        }
    }
};

参考推荐:

KMP字符串匹配算法

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • vim 快捷键技巧总结

    vi(vim)是上Linux非常常用的编辑器,很多Linux发行版都默认安装了vi(vim)。vi(vim)命令繁多但是如果使用灵活之后将会大大提高效率。vi是...

    阳光岛主
  • 【leetcode】Maximum Depth of Binary Tree

    Given a binary tree, find its maximum depth.

    阳光岛主
  • Linux 修改SSH 默认端口 22,防止被破解密码

    Linux/Unix 系统,很多人使用SSH + 密码来登陆服务器,默认 22端口,这样会有被暴力破解密码的危险(除非密码足够复杂且长度很长),因此最好修改SS...

    阳光岛主
  • [蓝桥杯][基础练习VIP]字符串对比

    用户7727433
  • KafkaController分析5-Partition状态机

    扫帚的影子
  • 足球大数据:统计和分析之间岂止一步之遥

    我们当然希望从这些简单的描述性的统计数据背后能够挖掘出更多关于足球比赛本质的信息。虽然这方面已经开展了很多工作,也有了一些进展,但是还只是在萌芽阶段。 ? 相...

    小莹莹
  • Kafka 简介

    在Kafka中,客户端和服务器之间的通信是通过一种简单的,高性能的,语言不可知的TCP协议完成的。

    小忽悠
  • OpenCV中直方图反向投影算法详解与实现

    OpenCV中直方图反向投影算法详解与实现 一:直方图交叉 OpenCV中直方图反向投影算法实现来自一篇论文《Indexing Via Color Histog...

    OpenCV学堂
  • Kafka

    Kafka是一种高吞吐量的分布式发布订阅消息系统,它可以处理消费者规模的网站中的所有动作流数据。 这种动作(网页浏览,搜索和其他用户的行动)是在现代网络上的许多...

    HUC思梦
  • 鹅厂揭秘——高端大气的App电量测试

    如何评价我们开发出来的应用是耗电还是不耗电,如何测试?这就是我们今天讨论的主题——电量测试,一个在移动应用中新出现的测试类型。 作者简介 ? 袁建发 腾讯智能...

    腾讯Bugly

扫码关注云+社区

领取腾讯云代金券