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 mn, 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语言入门 C语言_leetcode题解之28-implement-strstr.c
js js_leetcode题解之28-implement-strStr().js
c c语言_leetcode 0028_implement_strstr.zip
strStr-fail-fast.js的解决方案,也使用了自顶向下的迭代方法,但被设计为在遇到边缘情况时快速下降。 这提高了性能,几乎 100% 击败了之前所有的 Leetcode 提交。 示例 1: Input: haystack = "hello", needle = ...
Implement strStr() 实现找字串功能 lint158 anagrams 两个乱序字符串的比较 lint55 compare-string和group string都是同型题目 int79-LCS lintcode上的79题 寻找最长公共字串 lintcode 138-Subarray-Sum integer-...
ImplementstrStr.java //28. Implement strStr() │ LongestIncreasingSubsequence.java 300.Longest Increasing Subsequence | LongestPalindromicSubstring.java 5. Longest Palindromic Substring │ RansomNote...
LeetCode 的第 28 题“实现 strStr()”是一个经典的字符串搜索问题,要求我们在给定的字符串(haystack)中查找另一个字符串(needle)首次出现的位置。如果找不到,返回 -1。这个题目旨在考察对字符串处理的理解和...
Implement strStr() 解决方法:KMP 2018-08-22 20:05 LeetCode: 57. Insert Interval 解决方法:遍历 LeetCode: 229. Majority Element II 解决方法:Majority Voting算法的变种。但是最终的算法实现形式,很难理解...
Leetcode扑克 Leetcode Starting from 2020/08/02 Leetcode practice with Python ...Implement strStr() 实现 strStr() String / 字符串 循环遍历即可 algorithm-pattern: quick start 43 Multiply S
leetcode 516 8/13 - 8/18 周:leetcode#: 409. ...28. Implement strStr() 5. Longest Palindromic Substring option: 516. Longest Palindromic Subsequence string replacement strStr II 链接:
Implement strStr() String to Integer (atoi) addBinary longestPalindrome maximal rectangle :dp问题,较难 largestRectangleArea 求直方图的最大面积,左右两次扫面+剪枝优化 Valid Parentheses 用栈判断括号...
leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持对于数据结构的熟悉。 ** Leetcode 题目列表 005 Longest Palindromic Substring ...Implement strStr() 031 Next Permutat
- Implement strStr(): 实现字符串的查找功能,类似于C语言中的strstr()函数。 - Divide Two Integers: 实现整数除法,不能使用乘法、除法和模运算符。 - Search in Rotated Sorted Array: 在旋转过的排序数组中进行...
比如,实现strStr()函数(Implement strStr())和有效的括号(Valid Parentheses)等,需要深入理解字符串操作和正则表达式。 6. **哈希表**:哈希表提供高效的查找和插入操作,常用于解决查找重复项、最近点对等...
1_TwoSum 9_PalindromeNumber 13_RomanToInteger 14_LongestCommonPrefix 20_ValidParentheses 21_MergeTwoSortedLists 26_RemoveDuplicatesFromSortedArray 27_RemoveElement 28_ImplementStrStr() 35_Search...
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
28-implement-strstr.c 知识管理计划(完成)和 Boyer-Moore 算法。 使用 manacher 算法更新 5-longest-palindromic-substring.c。 (完毕) 使用优化算法更新 214-shortest-palindrome.c。 使用二分搜索更新 287-...
- Implement strStr(实现strStr函数) - Two Strings Are Anagrams(两个字符串是否为字母异位词) - Compare Strings(比较字符串) - Group Anagrams(字母异位词分组) - Longest Common Substring(最长...
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