1. Description of the problem
Original link leetcode-cn.com/problems/im…
English description
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().
Example 1:
Input: haystack = “hello”, needle = “ll”
Output: 2Example 2:
Input: haystack = “aaaaa”, needle = “bba”
Output: -1Example 3:
Input: haystack = “”, needle = “”
Output: 0Constraints:
- 0 <= haystack.length, needle.length <= 5 * 10^4
- haystack and needle consist of only lower-case English characters.
Product description
Implement the strStr() function.
Given a Haystack string and a Needle string, find the first position in the Haystack string where the Needle string appears (starting from 0). If none exists, -1 is returned.
Example 1:
Input: haystack = “hello”, needle = “ll” Output: 2
Example 2:
Input: haystack = “aaAAA “, needle = “bba” Output: -1
Description:
- What value should we return when needle is an empty string? This is a good question to ask in an interview.
- For this case, we should return 0 when needle is an empty string. This is consistent with the C language STRSTR () and the Java definition of indexOf().
Source: LeetCode link: leetcode-cn.com/problems/im… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
Second, the idea of solving the problem
Reference:
@test 【Sunday solution 】 The implementation of Sunday algorithm is introduced in detail.
@loliconautomaton [String matching — Brute-Force, Sunday, and KMP] introduces the differences between different algorithms and why they work;
【 (original) explain KMP algorithm 】 Introduce the principle of KMP algorithm in detail;
1. Sunday algorithm
1.1 Algorithm Implementation
Graph source @test 【Sunday 解 释 】 Big guy explain of very clear, took over directly to use
1.2 Algorithm Principle
If the template string (Pattern) fails to match the current substring (curString), we need to consider retrieving the substring (curString) from the right and comparing it with pattern.
The usual brute force solution is to “move one bit to the right honestly” and take a new substring from the current position.
The Sunday algorithm computes the shortest distance that you have to move. Here’s an example:
Assume that the original string is srcString, the current string is curString, the character following curString is nextChar, and the pattern string is pattern.
Example 1: nextChar is not in the pattern
Of course you can skip nextChar and lock the pointer directly to the next position of nextChar, which is 4.
The shortest movement distance is pattern.size() + 1:
Example 2: nextChar is the last character of pattern
Our best guess is that if we move one bit to the right, it’s an exact match, so the shortest distance is 1;
Example 3: nextChar is the penultimate character of pattern
For the best guess, the string in the red box is Pattern, so the shortest distance is 2;
Example 4: There are repeated characters in pattern
In the implementation of the algorithm, write: [store every character that appears in the pattern string, the distance from the right-most position to the tail in the pattern string +1].
So the shortest distance here is 1, not 3, so you don’t miss the right answer.
2. KMP algorithm
Reference @gu ~ shadow [(original) detailed explanation of KMP algorithm], very detailed! Here are the key excerpts for the record.
public static int[] getNext(String ps) {
char[] p = ps.toCharArray();
int[] next = new int[p.length];
next[0] = -1;
int j = 0;
int k = -1;
while (j < p.length - 1) {
if (k == -1 || p[j] == p[k]) {
next[++j] = ++k;
} else {
k = next[k];
}
}
return next;
}
Copy the code
Three, AC code
Sunday algorithm
C++
class Solution { public: int strStr(string haystack, string needle) { unordered_map<char, int> shift; int index = 0; For (int I = 0; i < needle.size(); i++) { shift[needle[i]] = needle.size() - i; } while(index + needle.size() <= haystack.size()) { If (haystack. Substr (index, needle. Size ()) == needle) return index; Int nextCharIndex = index + needle. Size (); If (nextCharIndex >= haystack.size()) return -1; if(nextCharIndex >= haystack.size()) return -1; if(shift.find(haystack[nextCharIndex]) == shift.end()) { index = index + needle.size() + 1; } else { index += shift[haystack[nextCharIndex]]; } } return -1; }};Copy the codeJava
S.char (index) is used to locate characters in a string.
The string interception function substring() takes two arguments with left and right boundaries, unlike C++ substr;
Class Solution {public int strStr(String haystack, String needle) { Shift = new HashMap<String, Integer>(); int index = 0; for(int i = 0; i < needle.length(); i++) { shift.put(String.valueOf(needle.charAt(i)), needle.length() - i); } while(index + needle. Length () <= haystack.length()) { I'm checking if the strings are the same, StringBuilder curString = new StringBuilder(haystack.subString (index, index + needle. Length ()))); // if(needle.equals(curString.toString())) return index; if(needle.equals(haystack.substring(index, index + needle.length()))) return index; Int nextCharIndex = index + needle. Length (); int nextCharIndex = index + needle. If (nextCharIndex >= haystack.length()) return -1; if(nextCharIndex >= haystack.length()) return -1; // String key = String.valueof (haystack.charat (nextCharIndex)); if(shift.get(key) == null) { index = index + needle.length() + 1; } else { index += shift.get(key); } } return -1; }}Copy the codeKMP algorithm
C++
Note that the size() function returns an unsigned number, which requires a cast when compared to a signed number
class Solution { public: vector<int> getNext(string ps) { vector<int> next(ps.size(), -1); // Initialize next array to -1 if(ps.size() == 0) return next; Int j = 0, k = -1; int j = 0, k = -1; while(j < ps.size() - 1) { if(k == -1 || ps[j] == ps[k]) { if(ps[++j] ! = ps[++k]) { next[j] = k; } else { next[j] = next[k]; } } else if(ps[j] ! = ps[k]) { k = next[k]; }} return next;}} return next;}} return next; } int strStr(string haystack, string needle) { int i = 0; int j = 0; Vector <int> next = getNext(needle); Needle. Size (); needle. Size (); needle. Size (); Ensure that the right conditions while (I < haystack. The size () && j < int (needle. The size ())) {if (j = = 1 | | haystack [I] = = needle [j]) {i++; j++; } else { j = next[j]; } } if(j == needle.size()) { return i - j; } else { return -1; }}};Copy the codeJava
class Solution { public static int[] getNext(String ps) { char[] p = ps.toCharArray(); int[] next = new int[p.length]; if(p.length == 0) return next; next[0] = -1; int j = 0; int k = -1; while (j < p.length - 1) { if (k == -1 || p[j] == p[k]) { if(p[++j] ! = p[++k]) { next[j] = k; } else { next[j] = next[k]; } } else { k = next[k]; } } return next; } public int strStr(String haystack, String needle) { char[] t = haystack.toCharArray(); char[] p = needle.toCharArray(); int i = 0; Int j = 0; Int [] next = getNext(needle); While (I < t.l ength && j < p.l ength) {if (j = = | | t = = p [j] [I]) {/ / when j to 1, to move the I, j, of course, also want to 0 i++; j++; } else { j = next[j]; }} if (j == p.length) {return i-j; } else { return -1; }}}Copy the codeFourth, the problem solving process
The first,
I do the same ε(┬┬﹏┬┬)3
Anyway, we’re gonna start with the usual violence
class Solution { public: int strStr(string haystack, string needle) { for(int i = 0; i + needle.size() <= haystack.size(); i++) { if(haystack.substr(i, needle.size()) == needle) return i; } return -1; }};Copy the code
Do you have many question marks?
Don’t ask, to ask is to know nothing (⓿_⓿)
The second stroke
Using the Sunday algorithm…
The third stroke
Using the KMP algorithm…
