KMP算法的实现

KMP1.java

public class KMP1 {
    public static int kmp1(String pattern,  String src){
        int srcLength = src.length() ;
        int patternLength = pattern.length() ;
        int index = -1 ;
        int count = 0 ;
        for(int i = 0 ; i < srcLength - 1 ;){
            count = 0 ;
            for(int j = 0 ; (j < patternLength ) && (i < srcLength) ; j++){
                if(src.charAt(i) == pattern.charAt(j)){
                    count++ ;
                    i++ ;
                }else{
                    break ;
                }
            }
            if(count == patternLength){
                return i - count ;
            }
            if(count == 0){
                i++ ;
            }
        }
        return index ;
    } 


    public static void main(String[] args){
        String src = "1234567890abcdefghijk" ;
        String pattern = "abcd" ;
        long beginTime = System.nanoTime() ;
        int index = kmp1(pattern, src) ;
        System.out.println("My KMP : index = " + index + " and time = " + (System.nanoTime() - beginTime) + "ns");
        beginTime = System.nanoTime() ;
        index = src.indexOf(pattern) ;
        System.out.println("String.indexOf : index = " + index + " and time = " + (System.nanoTime() - beginTime) + "ns");
    }
}

KMP2.java

    public static int kmp2(String pattern,  String src){
        int srcLength = src.length() ;
        int patternLength = pattern.length() ;
        int index = -1 ;
        int count = 0 ;
        for(int i = 0 ; i < srcLength - 1 ;){
            count = 0 ;
            for(int j = 0 ; (j < patternLength ) && (i < srcLength) && (src.charAt(i) == pattern.charAt(j)); j++,i++,count++) ;
            if(count == patternLength){
                return i - count ;
            }
            if(count == 0){
                i++ ;
            }
        }
        return index ;
    } 

KMP2执行结果

效果依然不好： 

My KMP : index = 10 and time = 55805 ns
String.indexOf : index = 10 and time = 10277 ns

后续还需要再修改才行

KMP3.java

    public static int kmp3(char[] patternArray , char[] srcArray){
    	int index = -1 ;
        int count = 0 ;
        for(int i = 0 ; i < srcArray.length - 1 ;){
            count = 0 ;
            for(int j = 0 ; (j < patternArray.length ) && (i < srcArray.length) && (srcArray[i] == patternArray[j]); j++,i++,count++) ;
            if(count == patternArray.length){
                return i - count ;
            }
            if(count == 0){
                i++ ;
            }
        }
        return index ;
    }

KMP3输出结果

结果很悲剧，输出如下 
My KMP : index = 10 and time = 58012 ns
String.indexOf : index = 10 and time = 9895 ns

对代码进行修改，发现方法kmp1在内层循环中对条件判断的使用有些费操作，遂修改如下：