/**
 * kmp算法變種實現(xiàn)模糊的模式匹配方法
 * 如：大賊王在這男人處，匹配，我是要成為海賊王的男人；
 * 可以匹配出賊王，返回 “賊王”；
 * 或返回模式串“大賊王在這男人處”關(guān)于 賊王、男人 的位置，與匹配串 我是要成為海賊王的男人 關(guān)于 賊王、男人 的位置
 * 時間復(fù)雜度：
 * 空間復(fù)雜度：
 * @author Administrator
 */
public class KmpFuzzyUtils {

    private static List<PatternLocation> getFuzzyMatching(String input, String target){
        try{
            int m = input.length();
            int n = target.length();
            if(m <= 0 || n <= 0){
                return Collections.emptyList();
            }
            List<PatternLocation> list = new ArrayList<>();

            Integer count = 0;

            for(int i = 0; i < m; ++i){
                for(int j = 0; j < n; ++j){
                    if(input.charAt(i) == target.charAt(j)){
                        count = i;

                        //都需要注意邊界效應(yīng)
                        grandson:
                            for(int x = j ; x < n && count < m; ++x){
                                System.out.println(input.charAt(count) + " xxxxx " + target.charAt(x));
                                if(input.charAt(count) != target.charAt(x)){
                                    PatternLocation patternLocation = new PatternLocation();
                                    patternLocation.setStart(j);
                                    patternLocation.setEnd(x);
                                    patternLocation.setValue(target.substring(j,x));

                                    list.add(patternLocation);
                                    break grandson;
                                }else {
                                    if(count+1 >= m || x+1 >= n){
                                        x++;
                                        PatternLocation patternLocation = new PatternLocation();
                                        patternLocation.setStart(j);
                                        patternLocation.setEnd(x);
                                        patternLocation.setValue(target.substring(j,x));

                                        list.add(patternLocation);
                                        break grandson;
                                    }
                                }
                                count++;
                            }
                    }
                }
            }

            return list;
        }catch (Exception e){
            e.printStackTrace();
        }
        return Collections.emptyList();
    }

    public static void main(String[] args) {
        List<PatternLocation> matchs = getFuzzyMatching("大賊王在這男人處", "我是要成為海賊王的男人還好大");
        System.out.println(matchs);
    }

}