Implement strStr()

参考:https://leetcode.com/problems/implement-strstr/

問題の内容:

haystackの中にneedleが最初に現れるIndexを返し、ないの場合は-1を返します。
明確にします。
ちなみに、needleが空の文字列の場合、何を返すべきでしょうか？

例:

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

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

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

ヒント:

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

この問題の解答は、普通のForLoopでできます、
又はKMP法を使って、回答します。
KMP法の中に、一番理解難しいのは、多分PartialMatchTableの事です、
PartialMatchTableとは、指定のStringの中に、prefixとsuffix イコールの部分です。
abcdabの場合
a -> 0
ab -> [prefix: a ,suffix: b] ->0
abc ->[prefix: a,ab ,suffix: c,bc] ->0
abcd ->[prefix: a,ab,abc ,suffix: d,dc,dcb] ->0
abcda ->[prefix: a,ab,abc,abcd ,suffix: a,ad,adc,adcb] ->　aは両方の中に共に出ました、 1です
abcdab ->[prefix: a,ab,abc,abcd,abcda ,suffix: b,ba,bad,badc,badcb] ->0
この場合：
abcdabのPartialMatchTableは
000010 です

class Solution {
    fun strStr(haystack: String, needle: String): Int {
        var m = needle.length
        var n = haystack.length
        if(m == 0){
            return 0
        }
        val pi = IntArray(m)
        var j = 0
        for(i in 1 until m){
            while(j > 0 && needle[j] != needle[i]){
                j = pi[j-1]!!
            }
            if(needle[i] == needle[j]){
                j++
            }
            pi[i] = j
        }

        var jj = 0
        for(i in 0 until n){
            while(jj > 0 && haystack[i] != needle[jj]){
                jj = pi[jj-1]!!
            }
            if(haystack[i] == needle[jj]){
                jj++
            }
            if(jj == m){
                return i - m + 1
            }
        }
        return -1
    }
}