【LeetCode】No.28. Implement strStr

题目链接： https://leetcode.com/problems/implement-strstr/

1. 题目介绍（strStr()）

Implement strStr().

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

【Translate】： 给定两个字符串“needle”和“haystack”，返回“needle”在“haystack”中第一个出现的索引，如果“needle”不属于“haystack”，则返回“-1”。

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

【Translate】： 当指针是空字符串时，我们应该返回什么?这是一个很好的面试问题。

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

【Translate】： 对于这个问题，当needle为空字符串时，我们将返回0。这与C的strstr()和Java的indexOf()是一致的。

【测试用例】：

【约束】：

2. 题解 2.1 indexOf()

  这样的做法无疑就是耍赖了，因为题目让我实现的就是indexOf()。

    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

2.2 Conventional Thinking

  iziang提供的题解 Share my accepted java solution。常规思路了，把可能的三种情况分别进行了判断。

    public int strStr(String haystack, String needle) {
        int l1 = haystack.length(), l2 = needle.length();
        if (l1 < l2) {
            return -1;
        } else if (l2 == 0) {
            return 0;
        }
        int threshold = l1 - l2;
        for (int i = 0; i <= threshold; i++) {
            if (haystack.substring(i,i+l2).equals(needle)) {
                return i;
            }
        }
        return -1;
    }

2.3 KMP

   cdai在Accepted KMP solution in java for reference的评论中提供的题解。

    // Similar to strStr except compare t against itself
    private int[] computePrefixFunc(String t) {
        int[] f = new int[t.length()];
        for (int i = 1, j = 0; i < t.length(); i++) { // now i = #matched
            while (j > 0 && t.charAt(i) != t.charAt(j)) j = f[j - 1];
            if (t.charAt(i) == t.charAt(j)) j++;
            f[i] = j;
        }
        return f;
    }
    
    public int strStr(String s, String t) {
        int[] f = computePrefixFunc(t);
        int i, j;
        for (i = 0, j = 0; i < s.length() && j < t.length(); i++) { // never back up i
            while (j > 0 && s.charAt(i) != t.charAt(j)) j = f[j - 1]; // back up j recursively till next char match
            if (s.charAt(i) == t.charAt(j)) j++; // if matched move j, otherwise give up current i and move on
        }
        return j == t.length() ? i - j : -1;
    }

3. 可参考

[1] 什么是KMP算法（详解）
[2] KMP算法详解