leetcode第28题字符串匹配

注解：需要考虑一些特殊的边界值：needle为0，needle比haystack大

暴力求解

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length()==0)return 0;
        for(int i=0;i<haystack.length()-needle.length()+1;i++){
            int flag = 0;
            for(int j=0;j<needle.length();j++){
                if(needle.charAt(j)==haystack.charAt(i+j)){
                    flag++;
                }else{
                    break;
                }
            }
            if(flag == needle.length())return i;
        }
        return -1;
    }
}

KMP算法

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length()==0)return 0;
        int [] nextval = new int[999999];
        getNext(needle,nextval);
        int i=0;int j=0;
        while(i<haystack.length()&&j<needle.length()){
            if(j==-1||haystack.charAt(i)==needle.charAt(j)){
                i++;j++;
            }else{
                j=nextval[j];
            }
        }
        if(j>=needle.length()) return i-needle.length();
        else return -1;
    }
    
 public void getNext(String needle,int [] nextval){
     int i=1;int j=0;nextval[0]=-1;//这个地方比较容易写错，要注意一下边界值
     while(i<needle.length()){
         if(j==-1||needle.charAt(i)==needle.charAt(j)){
             i++;j++;
             if(i>=needle.length())break;
             if(needle.charAt(i)==needle.charAt(j))nextval[i]=nextval[j];
                 else nextval[i]=j;
         }else{
             j=nextval[j];
         }
     }
 }   
    
    
}