KMP字符串匹配

KMP字符串匹配

package com.zjr.wholesale.config;

import java.util.ArrayList;
import java.util.List;

public class KMP {

    /*public static String [] str = new String[]{"b","a","c","b","a","d",
            "a","b","a","d","a","b","a","b","a","c","a","m","b","a","b","a","c","a","d","d","a","b","a","b","a","c","a","s","d"};
    public static String [] ptr = new String[]{"a","b","a","b","a","c","a"};*/


    public static String [] str = new String[]{"a","b","c","a","a","b",
            "a","b","a","b","a","a"};
    public static String [] ptr = new String[]{"a","b","a","b"};

    public static void main(String []args) {
        List array = getPtrArray(ptr);
        ifEquals(0,0,array);
    }

    //递归判断字符串比较
    public static void ifEquals(int i,int j,List array){
        if(i < str.length){
            if(j < ptr.length){
                if(str[i].equals(ptr[j])){
                    i++;
                    j++;
                    ifEquals(i,j,array);
                }else{
                    if(j == 0){
                        i++;
                    }else{
                        int length = getArrayValue(j,array);
                        if(length != 0){
                            i = i - length;
                        }
                        j = 0;
                    }
                    ifEquals(i,j,array);
                }
            }else{
                System.out.println("Ptr 匹配成功，下标开始位置为:" + (i - ptr.length));
                j = 0;
                ifEquals(i,j,array);
            }
        }else{
            System.out.println("字符串匹配结束");
        }
    }

    //获取前缀后缀数组中的长度
    public static int getArrayValue(int j,List array){
        return array.get(j-1);
    }

    //获取比较字符串的前缀后缀数组
    public static List getPtrArray(String []str){
        int j = 1;
        List array = new ArrayList();
        while(j <= str.length){
            List nStr = new ArrayList();
            for(int i=0;i nStr){
        int length = 0;
        if(nStr.size() == 1){
            length = 0;
        }else{
            int i = nStr.size();
            boolean flag = true;
            while(i > 0 && flag){
                i--;
                StringBuilder str = new StringBuilder();
                StringBuilder ptr = new StringBuilder();
                for(int index = 0;index < i;index++){
                    str.append(nStr.get(index));
                }
                for(int lIndex=(nStr.size() - i);lIndex < nStr.size();lIndex++){
                    ptr.append(nStr.get(lIndex));
                }
                if(str.toString().equals(ptr.toString())){
                    flag = false;
                    length = str.length();
                }
            }
        }
        return length;
    }
}