Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Update (2014-11-02):
The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button to reset your code definition.
Solution:
1 public class Solution { 2 public int strStr(String haystack, String needle) { 3 if (needle.isEmpty()) return 0; 4 if (haystack.isEmpty()) return -1; 5 6 int[] pm = getPartialMatchTable(needle); 7 int p1 = 0, p2 = 0; 8 while (p1<haystack.length() && p2<needle.length()){ 9 if (haystack.charAt(p1)==needle.charAt(p2)){ 10 p1++; 11 p2++; 12 } else { 13 if (p2==0) p1++; 14 else p2 = pm[p2-1]+1; 15 } 16 } 17 if (p2<needle.length()) return -1; 18 else return p1-p2; 19 20 } 21 22 public int[] getPartialMatchTable(String needle){ 23 int[] pm = new int[needle.length()]; 24 pm[0] = -1; 25 for (int i=1;i<needle.length();i++){ 26 int j = pm[i-1]; 27 while (j>=0 && needle.charAt(i)!=needle.charAt(j+1)) j = pm[j]; 28 if (needle.charAt(i)==needle.charAt(j+1)) pm[i] = j+1; 29 else pm[i] = -1; 30 } 31 return pm; 32 } 33 }
LeetCode-Implement strStr()-KMP
原文：http://www.cnblogs.com/lishiblog/p/4200270.html