/**
 * kmp算法变种实现模糊的模式匹配方法
 * 如：大贼王在这男人处，匹配，我是要成为海贼王的男人；
 * 可以匹配出贼王，返回 “贼王”；
 * 或返回模式串“大贼王在这男人处”关于 贼王、男人 的位置，与匹配串 我是要成为海贼王的男人 关于 贼王、男人 的位置
 * 时间复杂度：
 * 空间复杂度：
 * @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;

                        //都需要注意边界效应
                        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);
    }

}