题目：
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
翻译：
找到字符串的子串位置，并返回。如果没有则返回-1
思路：
通过最简单的BF遍历，如果不符合则指向下一个字符，最后如果长度等于子串长度，则返回位置。
代码：
public static int strStr(String haystack, String needle) {if(haystack == null || needle == null)return 0;if(haystack.length() < needle.length())return -1;int hlen = haystack.length();int nlen = needle.length();for(int i = 0 ; i <= hlen – nlen;i++){int j = 0;for(;j < nlen;j++){if(needle.charAt(j)!=haystack.charAt(i+j))break;}if(j == nlen)return i;}return -1;}还有一种方法是KMP。虽说前些日子看了KMP，但让自己动手写起来还是难度有点大。
于是，又重新复习了一遍。贴上KMP的算法。
public static void getNext(String str,int next[]){int j = 0;int k = -1;next[0] = -1;int len = str.length();while(j < len-1){if(k == -1 || str.charAt(k) == str.charAt(j)){j++;k++;next[j] = k;}else {k = next[k];}}}public static int KMP(String str,String temp){int i = 0;int j = 0;int slen = str.length();int tlen = temp.length();int []next = new int[tlen];getNext(temp, next);while(i < slen && j < tlen){if(str.charAt(i) == temp.charAt(j)){i++;j++;}else {if(next[j] == -1){i++;j = 0;}else {j = next[j];}}if(j == tlen)return i – j;}return -1;}/** * @param args */public static void main(String[] args) {// TODO 自动生成的方法存根String str = "ABC ABCDAB ABCDABCDABDE";String pattern = "ABCDABD";int i = KMP(str,pattern);System.out.println(i);}原理就是找到next的数组。然后在遍历的时候如果匹配则返回，没有匹配则跳指向next数组对应的位置，继续扫描判断。 还是部分细节的处理掌握不牢固。以后多看看。
后来查看大神的写法，发现了一个不错的。采用rolling hash。
链接：
基本思想是用一个hashcode来表示一个字符串，为了保证hash的唯一性，，我们用比字符集大的素数为底，以这个素数的幂为基。举例来说，字符集是小写字母集，取素数29为底。比如字符串“abacd",转化为hashcode=1+2*29+1*29^2+3*29^3+4*29^4。然后是如何在前进一步的时候计算新的hashcode，比如匹配串是原串是”abacde“，匹配串长度为5，根据以上的方法计算”abacd“的hashcode=h，那么下一步”bacde“的hashcode=h/29+5*29^4。这是一个constant的操作，所以检测所有子串的时间复杂度只需要O(m+n-m)=O(n)，也是一个线性算法。
public String strStr(String haystack, String needle) {if(haystack==null || needle==null) return null;if(haystack.length()==0){return needle.length()==0?"":null;}if(needle.length()==0) return haystack;if(haystack.length()<needle.length()) return null;int base = 29; long patternHash = 0;long tempBase = 1;for(int i=needle.length()-1; i>=0; i–){patternHash += (int)needle.charAt(i)*tempBase;tempBase *= base;}long hayHash = 0;tempBase = 1;for(int i=needle.length()-1; i>=0; i–){hayHash += (int)haystack.charAt(i)*tempBase;tempBase *= base;}tempBase /= base;if(hayHash == patternHash){return haystack;}for(int i=needle.length(); i<haystack.length(); i++){hayHash = (hayHash – (int)haystack.charAt(i-needle.length())*tempBase)*base+(int)haystack.charAt(i);if(hayHash == patternHash){return haystack.substring(i-needle.length()+1);}}return null; }
若不给自己设限，则人生中就没有限制你发挥的藩篱。
