KMPアルゴリズムjava版の実装

原理：http://www.ruanyifeng.com/blo...コード

import java.util.Arrays;

public class KMP {
    private static int[] prefixTable;

    /**
     *      
     * @param t
     * @return
     */
    public int[] getPrefixTable(char[] t){
        int n = t.length;
        int len;//    
        prefixTable = new int[n];
        prefixTable[0] = 0;

        for(int i = 1;i < n;i++){
            len  = prefixTable[i - 1];
            while(true){
                if(t[len] == t[i]){
                    len++;
                    prefixTable[i] = len;
                    break;
                }else{
                    if(len > 0)//       
                        len = prefixTable[len - 1];
                    else{
                        prefixTable[i] = 0;//
                        break;
                    }
                }
            }
        }
        return prefixTable;
    }

    public int[] match(char[] s,char[] t){
        int[] result = new int[s.length];//         
        int count = 0;
        int j = 0;//        
        for(int i = 0;i < s.length;i++){
            if(s[i] == t[j]){//  
                if(j == t.length - 1){//      ，    ，  j=0         
                    result[count++] = i - t.length + 1;
                    j = 0;
                }else{//       1
                    j++;
                }
            }else{
                if(j > 0){//      ＞0
                    j = prefixTable[j - 1];//                     
                    i--;//    
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        KMP kmp= new KMP();
        char[] s = "ABCDAB ABCDABCDABDEABCDABD".toCharArray();
        char[] t = "ABCDABD".toCharArray();
        kmp.getPrefixTable(t);
        int index[] = kmp.match(s, t);
        System.out.println(Arrays.toString(index));
    }
}

出力結果

[11, 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]