Question: 

题目:

Implement strStr().

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

---

 Solutions:

1. Naive Solution 很容易实现。O(n²) runtime.
2. Rolling Hash.  之前也实现过，O(n) runtime. 可是 hashcode 容易溢出，并且无法保证完全没有 Conflict。 减少 Conflict 可能性，是采用 BigInteger 来记录 hashcode 的值。
3. KMP Tutorial: 基本思路是寻找 pattern String 的 Prefix Pattern，不难理解

Naive Solution:

1 public int strStr(String haystack, String needle) { 2     if(haystack == null) { 3         return -1; 4     } 5      6     if(needle == null) { 7         return haystack.length(); 8     } 9     10     if(haystack.length() < needle.length()) {11         return -1;12     }13     14     for(int i = 0; i <= haystack.length() - needle.length(); i++) {15         String tmp = haystack.substring(i, i+needle.length());16         if(tmp.equals(needle)) {17             return i;18         }19     }20     21     return -1;22 }