`

LeetCode 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.

Solution 1:

Naive method.

public int strStr(String a, String p) {
    int i, j, n = a.length(), m = p.length();
    for (i = 0, j = 0; j < m && i < n; i++, j++) {
        if (a.charAt(i) != p.charAt(j)) { 
            i -= j; 
            j = -1; 
        }
    }
    if (j == m) return i-m; 
    return -1;
}

 

Solution 2:

KMP method.

// KMP matching
public int strStr(String a, String p) {
    if(a == p || "".equals(p)) return 0;
    int i, j, n = a.length(), m = p.length();
    int[] next = preprocess(p);
    for (i = 0, j = 0; j < m && i < n; i++, j++) {
        while (j>=0 && a.charAt(i) != p.charAt(j)) { 
            j = next[j];
        }
    }
    if (j == m) return i-m;
    return -1; 
}
// KMP partial match table
private int[] preprocess(String pattern) {
    char[] p = pattern.toCharArray();
    int i = 0, j = -1, m=p.length;
    int[] b = new int[m+1];
    b[0] = j;
    while(i<m) {
        while(j>=0 && p[i] != p[j]) {
            j = b[j];
        }
        b[++i] = ++j;
    }
    return b;
}

After a shift of the pattern, the naive algorithm has forgotten all information about previously matched symbols. So it is possible that it re-compares a text symbol with different pattern symbols again and again. This leads to its worst case complexity of Θ(nm) (n: length of the text, m: length of the pattern).

The algorithm of Knuth, Morris and Pratt makes use of the information gained by previous symbol comparisons. It never re-compares a text symbol that has matched a pattern symbol. As a result, the complexity of the searching phase of the Knuth-Morris-Pratt algorithm is in O(n).

However, a preprocessing of the pattern is necessary in order to analyze its structure. The preprocessing phase has a complexity of O(m). Since m<=n, the overall complexity of the Knuth-Morris-Pratt algorithm is in O(n).

 

Reference:

http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm 

分享到:
评论

相关推荐

    C语言-leetcode题解之28-implement-strstr.c

    c语言入门 C语言_leetcode题解之28-implement-strstr.c

    js-leetcode题解之28-implement-strStr().js

    js js_leetcode题解之28-implement-strStr().js

    c语言-leetcode 0028-implement-strstr.zip

    c c语言_leetcode 0028_implement_strstr.zip

    leetcode跳动问题-Implement-strStr:实现strStr()。返回`haystack`中第一次出现`needle`的索引,

    strStr-fail-fast.js的解决方案,也使用了自顶向下的迭代方法,但被设计为在遇到边缘情况时快速下降。 这提高了性能,几乎 100% 击败了之前所有的 Leetcode 提交。 示例 1: Input: haystack = "hello", needle = ...

    leetcode2-code_interview:LeetCodeLintCode题解,剑指offer题目,互联网公司面试,BAT外企等面试题

    Implement strStr() 实现找字串功能 lint158 anagrams 两个乱序字符串的比较 lint55 compare-string和group string都是同型题目 int79-LCS lintcode上的79题 寻找最长公共字串 lintcode 138-Subarray-Sum integer-...

    leetcode信封-LeetCode:LeetCode解题

    ImplementstrStr.java //28. Implement strStr() │ LongestIncreasingSubsequence.java 300.Longest Increasing Subsequence | LongestPalindromicSubstring.java 5. Longest Palindromic Substring │ RansomNote...

    LeetCode 28. 实现 strStr()

    LeetCode 的第 28 题“实现 strStr()”是一个经典的字符串搜索问题,要求我们在给定的字符串(haystack)中查找另一个字符串(needle)首次出现的位置。如果找不到,返回 -1。这个题目旨在考察对字符串处理的理解和...

    leetcode答案-exercise-book:算法练习记录

    Implement strStr() 解决方法:KMP 2018-08-22 20:05 LeetCode: 57. Insert Interval 解决方法:遍历 LeetCode: 229. Majority Element II 解决方法:Majority Voting算法的变种。但是最终的算法实现形式,很难理解...

    Leetcode扑克-leetcode:Leetcode算法实践

    Leetcode扑克 Leetcode Starting from 2020/08/02 Leetcode practice with Python ...Implement strStr() 实现 strStr() String / 字符串 循环遍历即可 algorithm-pattern: quick start 43 Multiply S

    leetcode516-Lcode:代码

    leetcode 516 8/13 - 8/18 周:leetcode#: 409. ...28. Implement strStr() 5. Longest Palindromic Substring option: 516. Longest Palindromic Subsequence string replacement strStr II 链接:

    leetcode中国-leetcode:leetcode刷题

    Implement strStr() String to Integer (atoi) addBinary longestPalindrome maximal rectangle :dp问题,较难 largestRectangleArea 求直方图的最大面积,左右两次扫面+剪枝优化 Valid Parentheses 用栈判断括号...

    leetcode530-algorithm:算法

    leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持对于数据结构的熟悉。 ** Leetcode 题目列表 005 Longest Palindromic Substring ...Implement strStr() 031 Next Permutat

    _leetcode-python.pdf

    - Implement strStr(): 实现字符串的查找功能,类似于C语言中的strstr()函数。 - Divide Two Integers: 实现整数除法,不能使用乘法、除法和模运算符。 - Search in Rotated Sorted Array: 在旋转过的排序数组中进行...

    leetcode分类-leetcode:leetcode

    比如,实现strStr()函数(Implement strStr())和有效的括号(Valid Parentheses)等,需要深入理解字符串操作和正则表达式。 6. **哈希表**:哈希表提供高效的查找和插入操作,常用于解决查找重复项、最近点对等...

    Leetcode-Algorithm-Exercise

    1_TwoSum 9_PalindromeNumber 13_RomanToInteger 14_LongestCommonPrefix 20_ValidParentheses 21_MergeTwoSortedLists 26_RemoveDuplicatesFromSortedArray 27_RemoveElement 28_ImplementStrStr() 35_Search...

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...

    997leetcodec-myleetcode:我的leetcode解决方案

    28-implement-strstr.c 知识管理计划(完成)和 Boyer-Moore 算法。 使用 manacher 算法更新 5-longest-palindromic-substring.c。 (完毕) 使用优化算法更新 214-shortest-palindrome.c。 使用二分搜索更新 287-...

    算法刷题笔记leetcode/lintcode

    - Implement strStr(实现strStr函数) - Two Strings Are Anagrams(两个字符串是否为字母异位词) - Compare Strings(比较字符串) - Group Anagrams(字母异位词分组) - Longest Common Substring(最长...

    lrucacheleetcode-leetcode:leetcode

    lru缓存leetcode leetcode 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 5. Longest Palindromic ...28. Implement strStr() 3

Global site tag (gtag.js) - Google Analytics