String -- 28. Implement strstr()

1 Title Description

28. Realization strStr()
    Realization strStr() function .

Here are two strings haystack and needle , Please come in haystack Find in string needle The first place the string appears （ Subscript from 0 Start ）. If it doesn't exist , Then return to -1 .

explain ：

When needle When it's an empty string , What value should we return ？ This is a good question in an interview .

For this question , When needle When it's an empty string, we should return 0 . This is related to C Linguistic strstr() as well as Java Of indexOf() The definition matches .

2 Title Example

Example 1：
Input ：haystack = “hello”, needle = “ll”
Output ：2

Example 2：
Input ：haystack = “aaaaa”, needle = “bba”
Output ：-1

3 Topic tips

1 <= haystack.length, needle.length <= 104
haystack and needle It only consists of lowercase English characters

4 Ideas

This problem is the classic string single-mode matching model , Therefore, it can be solved by string matching algorithm , Common string matching algorithms include violent matching 、Knuth-Morris-Pratt Algorithm 、Boyer-Moore Algorithm 、Sunday Algorithm etc. , This article will explain Knuth-Morris-Pratt Algorithm .
Because the hash method may have the same hash values but different strings , and strStr Function requires that the matching result must be correct , Therefore, this article does not introduce the hash method , Interested readers can learn about the implementation of rolling hash by themselves ( Such as Rabin-Karp Algorithm ).
Method 1 : Violence matching ideas and algorithms
We can make the string needle And string haystack All the lengths of are m All substrings of match once .
To reduce unnecessary matching , Every time we fail to match, we immediately stop the matching of the current substring , Continue matching for the next substring . If the current substring matches successfully , We can return the starting position of the current substring . If all substrings fail to match , Then return to —1.
Complexity analysis
Time complexity :o(n x m), among n Is string hagystack The length of ,m Is string needle The length of . In the worst case, we need to put the string needle And string haystack All the lengths of are m All substrings of match once .
Spatial complexity :O(1). We just need a constant space to hold a few variables .
Method 2 ：KMP
No introduction , Too long , You can search for it yourself

5 My answer

Method 1 ： violence

class Solution {
    
    public int strStr(String haystack, String needle) {
    
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {
    
            boolean flag = true;
            for (int j = 0; j < m; j++) {
    
                if (haystack.charAt(i + j) != needle.charAt(j)) {
    
                    flag = false;
                    break;
                }
            }
            if (flag) {
    
                return i;
            }
        }
        return -1;
    }
}

Method 2 ：KMP

class Solution {
    
    public int strStr(String haystack, String needle) {
    
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
    
            return 0;
        }
        int[] pi = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
    
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
    
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
    
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
    
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
    
                j = pi[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
    
                j++;
            }
            if (j == m) {
    
                return i - m + 1;
            }
        }
        return -1;
    }
}