public int strStr(String haystack, String needle) {
	      if(needle==null||"".equals(needle))
		     return 0;
	      char a[]=haystack.toCharArray();
	      char b[]=needle.toCharArray();
		  for(int i=0;i<a.length-b.length+1;i++)
		  {
              int j=-1;
			  while(j++<b.length)
			  {
				  if(a[i+j]!=b[j])
				  {
					  break;
				  }
				  if(j==b.length-1)
					  return i; 
			 }
			  
		  }
		  return -1;
 }

public int strStr(String haystack, String needle) {
    int L = needle.length(), n = haystack.length();
    for (int start = 0; start < n - L + 1; ++start) {
      if (haystack.substring(start, start + L).equals(needle)) {
        return start;
      }
    }
    return -1;
  }

 public  int[] getNext(String needle) {
		    char[] p = needle.toCharArray();
		    int[] next = new int[p.length];
		    next[0] = -1;
		    int j = 0;
		    int k = -1;
		    while (j < p.length - 1) {
		       if (k == -1 || p[j] == p[k]) {
		           next[++j] = ++k;
		       } else {
		           k = next[k];
		       }
		    }
		    return next;
		}
	  public  int KMP(String haystack, String needle) {
		     char[] t = haystack.toCharArray();
		    char[] p = needle.toCharArray();
		    int i = 0; // 主串的位置
		    int j = 0; // 模式串的位置
		    int[] next = getNext(needle);
		    while (i < t.length && j < p.length) {
		       if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归0
		           i++;
		           j++;
		       } else {
		           // i不需要回溯了
		           // i = i - j + 1;
		           j = next[j]; // j回到指定位置
		       }
		       if(j==p.length) {return i-j;}
		    }
		    return -1;
		}
	  public int strStr(String haystack, String needle) {
		  if(needle==null||"".equals(needle))
		     return 0;
		 
		  return KMP(haystack, needle);
	 }

 public  int strStr(String haystack, String needle) {
		  if(needle==null||"".equals(needle))
			     return 0;
		  int lastchar[]=new int [200];
		  char a[]=haystack.toCharArray();
		  char p[]=needle.toCharArray();
		  for(int i=0;i<p.length;i++)
		  {
			  lastchar[p[i]]=i+1;
		  }
		  int i=0;
		  int j=0;
		 int len=a.length-p.length+1;
		  while (i<a.length) {
			 int index=i-(lastchar[a[i]]-1);//a[i] 字符
			if(lastchar[a[i]]!=0&&index>=0&&index<len)//可以匹配
			{
				while (j<p.length) {//尝试匹配
					if(p[j]!=a[index+j])
						break;
					j++;
				}
				if(j==p.length)
				{
					return index;
				}
				else {
					i=index+p.length;
					j=0;
				}
			}
			else {
				i++;
			}
		}
		  
		return -1;
	}