1 public class Solution {
 2     public String strStr(String haystack, String needle) {
 3         if(haystack==null) return null;
 4         int len1= haystack.length();
 5         int len2 = needle.length();
 6         if(needle==null||len2==0) return haystack;
 7         int i=0,j=0;
 8         char[] nee = needle.toCharArray();
 9         char[] hay = haystack.toCharArray();
10         int[] next  = getNext(nee,len2);
11         while(i<len1){
12             if(j==-1||hay[i]==nee[j]){
13                 i++;
14                 j++;
15                 if(j==len2){
16                     return haystack.substring(i-j);
17                 }
18             }
19             else{
20                 j= next[j];
21             }
22         }
23         return null;
24     }
25     
26     public int[] getNext(char[]nee,int len){
27         int i=0,j=-1;
28         int []next = new int[len];
29         next[0]=-1;
30         while(i<len-1){
31             if(j==-1||nee[i]==nee[j]){
32                 i++;
33                 j++;
34                 next[i]=j;
35             }
36             else{
37                  j=next[j];
38             }
39         }
40         return next;
41     }
42 }