> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/01-25-2022-28.md).

# 01/25/2022 28

Use two pointers.  iterate haystack and needle. If the character is same, increment j and i both. if j = needle.length, it means the needle is matched and return the index i -j. if the character is not same, then we need to set i = i -j +1, and j = 0 and compare them again. 

Time O(n\*m)

Space O(1)

class Solution { 

public int strStr(String haystack, String needle) { 

if(needle.length() == 0) return 0;

 if(haystack.length() == 0) return -1;

```
    int i = 0, j = 0, index = 0;
    while (i < haystack.length()){
        if (haystack.charAt(i) == needle.charAt(j)){
            i++;
            j++;
            
            if(j == needle.length()){
               return i-j; 
            } 
        }else{
            i = i -j +1;// need to remember this step!!!
            j = 0;
        }
    
    }
     return -1;
}   
```

}

Method 2: use KMP to avoid the unnecessay backtracking check and optimize the solution with Time O(n + m) and space O(m).

class Solution {&#x20;

public int strStr(String haystack, String needle) {

```
    if(haystack == null || needle == null || needle.length() > haystack.length()) return -1;
    if(needle.length() == 0) return 0;
    
    int[] table = kmpTable(needle);
    int i = 0, j = 0;
    while (i < haystack.length()){
        if(haystack.charAt(i) == needle.charAt(j)){
            i++;
            j++;
            if(j == needle.length()) return i-j;
        }else if (j > 0){
            j = table[j-1];
        }else{
            i++;
        }
    }
    return -1;
}

private int[] kmpTable(String pattern){
    int i = 1, j= 0;
    int length = pattern.length();
    int[] table = new int[length];
    
    while(i < length){
        if (pattern.charAt(i) == pattern.charAt(j)){
            j++;
            table[i] = j;
            i++;
        
        }else if(j > 0 ){
            j = table[j-1];
        }else{
            i++;
        }
    }
    
    
return table;
```

}

}