Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Implement strStr()

Leetcode algorithms 第 28 题:Implement strStr()。

题目

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

解答

字符串匹配问题。参考本博客KMP算法一文,下面提供两种算法的代码。

朴素算法代码如下:

class Solution {
public:    
    int strStr(char *haystack, char *needle) { //朴素算法
        int l1 = strlen(haystack), l2 = strlen(needle), i = 0, j = 0;
        while (i < l1 && j < l2)
            if (haystack[i] == needle[j]) i++, j++;
            else i -= j-1, j = 0;
        if (j == l2) return i - l2;
        else return -1;
    }
};

KMP算法代码如下:

class Solution {
public:
    int strStr(char *haystack, char *needle) { //KMP算法
        int l1 = strlen(haystack), l2 = strlen(needle), i = 0, j = 0;
        int next[100005]; getNext(needle, next);
        while (i < l1 && j < l2)
            if (j == -1 || haystack[i] == needle[j]) i++, j++;
            else j = next[j];
        if (j == l2) return i - l2;
        else return -1;
    }
    void getNext(char *t, int* next)
    {
        int l = strlen(t), i = 0, j = -1;
        next[0] = -1;
        while (i < l)
            if (j == -1 || t[i] == t[j]) next[++i] = ++j;
            else j = next[j];
        
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论