LeetCode 28 Implement strStr()は、文字列の戻り位置を見つけます.

タイトル:
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を採用します.
リンク:http://blog.csdn.net/linhuanmars/article/details/20276833
基本思想は1つのhashcodeで1つの文字列を表すことであり,hashの一意性を保証するために,文字セットより大きい素数をベースとし,この素数のべき乗をベースとする.例えば、文字セットは小文字セットであり、素数29をベースとする.例えば文字列「abacd」は、hashcode=1+2*29+1*29^2+3*29^3+4*29^4に変換されます.次に、マッチング列が元の列である「abacde」、マッチング列の長さが5であるなど、前のステップで新しいhashcodeを計算する方法です.以上の方法で「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()=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