28. Implement strStr()

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().

1
2
3
4
Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

1
2
3
4
Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

1
2
3
4
Example 3:

Input: haystack = "", needle = ""
Output: 0

Constraints:

0 <= haystack.length, needle.length <= 5 * 104
haystack and needle consist of only lower-case English characters.

Solution

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
class Solution {
    public int strStr(String haystack, String needle) {
        int[] zi = ziFunction(needle + "#" + haystack);
        int m = needle.length();
        if (m == 0) return 0;
        for (int i = 0; i < zi.length; i++) {
            if (zi[i] == m) {
                return i - m - 1;
            }
        } 
        return -1;
    }
    
    public int strStrNaive(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (m == 0) return 0;
        int i = 0;
        int j = 0;
         while (i < n) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
            if (j == m) {
                return i - j;
            } 
        } 
        return -1;
    }
    
    public int strStrKmp(String haystack, String needle) {
        int[] pi = prefixFunction(needle);
        int n = haystack.length();
        int m = needle.length();
        if (m == 0) return 0;
        int i = 0;
        int j = 0;
        while (i < n) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                if (j != 0)  {
                     j = pi[j - 1];
                } else {
                    i++;
                }
            }
            if (j == m){
                return i - j;
            } 
        } 
        return -1;
    }
    
    public int strStrPrefix(String haystack, String needle) {
        int[] pi = prefixFunction(needle + "#" + haystack);
        int m = needle.length();
        for (int i = 0; i < pi.length; i++) {
            if (pi[i] == m) {
                return i - m - m;
            }
        } 
        return -1;
    }
    
    int[] prefixFunction(String s) {
        int n = s.length();
        int[] pi = new int[n];
        
        for (int i = 1; i < n; i++) {
            // текущая длина префикса, который мы хотим продолжить
            // гарантируется, что s[0..j-1] = s[i-j..i-1].
            int j = pi[i - 1];
            
            //пока мы не можем продолжить текущий префикс
            while (j > 0 && s.charAt(i) != s.charAt(j)) { 
                j = pi[j - 1]; //уменьшаем его длину до следующей возможной
            }
            
            //Теперь j - максимальная длина префикса, который мы можем продолжить,
            //или 0, если такового не существует.
            
            if (s.charAt(i) == s.charAt(j)) {
                pi[i] = j + 1;
            } else {
                pi[i] = 0;
            }
        }
        return pi;
    }
    
    int[] ziFunction(String s) {
        int n = s.length();
        int[] zi = new int[n];
        int l = 0;
        for (int i = 1; i < n; i++) {
            //если i входит в уже обработанный отрезок
            //используем предыдущие вычисления
            zi[i] = Math.min(zi[l] + l - i, zi[i - l]); 
            zi[i] = Math.max(0, zi[i]);
            // иначе начальным значением z[i] остаётся 0
            // пытаемся увеличить z[i] наивным алгоритмом
            while (i + zi[i] < n && s.charAt(i + zi[i]) == s.charAt(zi[i])) {
                 zi[i]++;
            }
            //если мы можем увеличить r, делаем это
            if (i + zi[i] > l + zi[l]) {
                l = i;
            }
        }
        return zi;
    }
}

Solution#

Solution