題目：
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

翻譯：
實現一個方法strStr()。返回字符串needle第一次在字符串haystack出現的下標，如果needle不是haystack的一部分，就返回-1。

分析：
在文本中查找某個模式出現的位置的算法，稱為字符串匹配算法。常用的方法有樸素字符串匹配算法、KMP算法等。樸素字符串匹配算法，就是把2個字符串頭部對齊，然后逐一字符匹配，失配后，把needle右移一位，繼續從頭匹配。我們這里采用KMP算法。

代碼：

public class Solution {/*** 改進的Next指針算法** @param s* @return*/private int[] getNext(String s) {int[] next = new int[s.length()];next[0] = 0;if (s.length() == 1) {return next;}next[1] = 0;int i = 1;int j = 0;while (i < s.length() - 1) {if (s.charAt(i) == s.charAt(j)) {j++;i++;if (s.charAt(i) == s.charAt(j)) {next[i] = next[j - 1];} else {next[i] = j;}} else {if (j == 0) {i++;next[i] = 0;} else {j = next[j];}}}return next;}/*** KMP字符串匹配算法** @param s* @return*/public int strStr(String haystack, String needle) {if (needle.length() == 0) {return 0;}int[] next = getNext(needle);int index = -1;int i = 0;int j = 0;while (i < haystack.length()) {if (haystack.charAt(i) == needle.charAt(j)) {if (j == needle.length() - 1) {return i - j;}i++;j++;} else {if (j == 0) {i++;} else {j = next[j];}}}return index;} }

總結

以上是生活随笔為你收集整理的Leet Code OJ 28. Implement strStr() [Difficulty: Easy]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。