Implement strStr()
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
方法:KMP
正好趁这个题目温习了一下KMP字符串匹配。母串S, 模式串P
KMP算法是利用模式串P本身的特性来降低复杂度。通过next函数or覆盖函数来优化。
本质上,next函数/覆盖函数是overlap[i]是求出P[0~i]内的最大的前缀P[0~i-x]和后缀P[x~i]的长度。
#include <cstring> #include <iostream> using namespace std; class Solution { public: char *strStr(char *haystack, char *needle) { int lenh = strlen(haystack); int lenn = strlen(needle); if (lenn == 0) return haystack; int idx = kmp_search(haystack, needle, lenh, lenn); if (idx == -1) return NULL; else return haystack + idx; } int kmp_search(char* t, char* p, int lt, int lp) { int *over = new int[lp]; calc_overlap(over, p); int k = -1; for (int i = 0; i < lt; ++i) { while (k >= 0 && p[k+1] != t[i]) k = over[k]; if (p[k+1] == t[i]) k++; if (k == lp - 1) return i - k; } return -1; } void calc_overlap(int *over, char *str) { over[0] = -1; int k = -1; for (int i = 1; i < strlen(str); ++i) { while (k >= 0 && str[k+1] != str[i]) k = over[k]; if (str[k+1] == str[i]) k++; over[i] = k; } } };
N^2
class Solution { public: char *strStr(char *haystack, char *needle) { int l1 = strlen(haystack); int l2 = strlen(needle); if (l2 == 0) return haystack; char *s = haystack; while (*s != '\0') { if (l1 < l2) return NULL; if (cmp(s, needle)) return s; s++; l1--; } return NULL; } bool cmp(char* hay, char* ne) { while (*hay != '\0' && *ne != '\0') { if (*hay == *ne) { hay++, ne++; continue; } else return false; } if (*ne == '\0') return true; else return false; } };
相关推荐
题目来源:https://leetcode-cn.com/problems/implement-strstr 题目 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。...
ImplementstrStr.java //28. Implement strStr() │ LongestIncreasingSubsequence.java 300.Longest Increasing Subsequence | LongestPalindromicSubstring.java 5. Longest Palindromic Substring │ RansomNote...
leetcode跳动问题实现 strStr() 实现strStr() 。 返回 haystack 中第一次出现 Needle 的索引,如果needle不是haystack一部分,则返回-1 。 澄清: 当needle为空字符串时,我们应该返回什么? 这是面试时要问的一个很...
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
Leetcode扑克 Leetcode Starting from 2020/08/02 Leetcode practice with Python ...Implement strStr() 实现 strStr() String / 字符串 循环遍历即可 algorithm-pattern: quick start 43 Multiply S
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 Substring ...Implement strStr() 3
Implement strStr() String to Integer (atoi) addBinary longestPalindrome maximal rectangle :dp问题,较难 largestRectangleArea 求直方图的最大面积,左右两次扫面+剪枝优化 Valid Parentheses 用栈判断括号...
leetcode 516 8/13 - 8/18 周:leetcode#: 409. longestPalindrome ...Implement strStr() 5. Longest Palindromic Substring option: 516. Longest Palindromic Subsequence string replacement strStr II 链接:
Implement strStr() 解决方法:KMP 2018-08-22 20:05 LeetCode: 57. Insert Interval 解决方法:遍历 LeetCode: 229. Majority Element II 解决方法:Majority Voting算法的变种。但是最终的算法实现形式,很难理解...
leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持对于数据结构的熟悉。 ** Leetcode 题目列表 005 Longest Palindromic Substring ...Implement strStr() 031 Next Permutat
Implement strStr() 实现找字串功能 lint158 anagrams 两个乱序字符串的比较 lint55 compare-string和group string都是同型题目 int79-LCS lintcode上的79题 寻找最长公共字串 lintcode 138-Subarray-Sum integer-...
1_TwoSum 9_PalindromeNumber 13_RomanToInteger 14_LongestCommonPrefix 20_ValidParentheses 21_MergeTwoSortedLists 26_RemoveDuplicatesFromSortedArray 27_RemoveElement 28_ImplementStrStr() 35_Search...
28.Implement Strstr() KMP Hash BruteForce 35.Search Insert Position 二分法化简 2018/04/18: 29.Divide Two Integers 二进制累加代替除法,防止溢出 36.Valid Sudoku set去重复 2018/04/19: 038.Count and Say ...
28-implement-strstr.c 知识管理计划(完成)和 Boyer-Moore 算法。 使用 manacher 算法更新 5-longest-palindromic-substring.c。 (完毕) 使用优化算法更新 214-shortest-palindrome.c。 使用二分搜索更新 287-...
问题 完全的 017_Letter_Combinations_of_a_Phone_Number 018_4总和 019_Remove_Nth_Node_From_End_of_List ... 028_Implement_strStr() 029_Divide_Two_Integers 030_Substring_with_Concatenation_of
Implement strStr() String to Integer (atoi) Add Binary Longest Palindromic Substring Regular Expression Matching Wildcard Matching Longest Common Prefix Valid Number Integer to Roman Roman to Integer ...