[LeetCode] 28. Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

实现strStr(h, n)函数，如果在h中能找到n的完全匹配字符串，则返回对应的第一个字符的下标，否则返回-1。

思路： 经典的字符串匹配问题，就用经典的KMP算法来做，复杂度O(m+n)。

KMP

硬爆算法是若两个字符串h$h$和n$n$的当前字符hi$h_i$与nj$n_j$不匹配，j$j$从头开始，导致了复杂度变成了O(m*n)。 KMP算法是首先在短字符串n$n$中建立一个有匹配信息的next表，每当不匹配时，j$j$不是从头开始，而是直接跳到上一次已经匹配过的前缀开始，直接优化到了O(m+n)。

next表 next[i] = k表示了在字符串n中，从n[0-i]这一段字符串中，k长度的前缀与k长度的后缀完全匹配， next[0] = 0。 构造next表也可以理解为两个指针在短字符串n的匹配游走。

计算next表的算法： k表示当前已匹配的数量，也可以认为是当前遍历字符串前缀的下标。 i表示是当前字符串的下标。

匹配的算法： 计数器c表示已匹配的长度。 当h[i]与n[j]不匹配时，j=next[j-1]，回溯到n上已匹配的前缀位置开始比较，同时计数器c=next[j-1]。