Approximate matching

1.题意：

2.算法：

举例子
text "nothing",  pre "duno", post "ingenious"
在算text 与 pre时候，text从头开始match pre从尾巴看的最长
在算text与post时候，post从头开始match text从尾巴看的最长
因此问题可以转换为：求str1从头开始 match str2从尾巴看的最长

利用KMP第一步的table，把str1和str2连起来
还有一点就是text可以任意substring



在KMP第一步时候，在后边寻找开头那个pattern，后边可以从任意位置开始
对于post+'#'+text 很符合，text 的部分可以从任意位置开始，就是说任意substring
但是对于text+'#'+pre不符合，希望它可以变成post那步的形式。
发现reverse(pre),  reverse(text), 那么从pre尾巴看就变成了从pre头看，从text头看就变成了text尾巴看，只需要最后答案reverse回来即可
我们可以reverse(pre)+'#'+reverse(text)这样就和post那步一样了

 lps[i] = the longest proper prefix of pat[0..i] 
              which is also a suffix of pat[0..i]. 

lps[i] stores length of the maximum matching proper prefix which is also a suffix of the sub-pattern pat[0..i].

For the pattern “AAACAAAAAC”, lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/

 public static String approximateMatching(String s, String pre_text, String post_text){  
   String str1 = reverse(pre_text)+'*'+reverse(s);  
   String s1 = getMaxCommonPattern(str1,s,true);  
   String str2 = post_text+'*'+s;  
   String s2= getMaxCommonPattern(str2,s,false);  
   return s1.compareTo(s2) > 0 ? s2 : s1;  
 }  
 public static String getMaxCommonPattern(String str,String s,boolean reverse){  
   int n = str.length();  
 //  System.out.println(str);  
   int[] lps = new int[str.length()];  
   int len = 0,i = n-s.length();  
   int max = 0,j=0;  
   String maxMatch = "";  
   while(i < str.length() && len < n-s.length()){  
     if(str.charAt(i) == str.charAt(len)){  
       lps[i] = ++len;  
       if(max < lps[i]){  
         max = lps[i];  
         maxMatch = str.substring(i-len+1,i+1);  
         j = i-len+1;  
       }  
       if(max == lps[i]&&maxMatch.compareTo(str.substring(i-len+1,i+1))>0){  
         maxMatch = str.substring(i-len+1,i+1);  
         j = i-len+1;  
       }  
       i++;  
     }else{  
       if(len == 0)  
         i++;  
       else  
         len = lps[len-1];  
     }  
   }  
 //  System.out.println(str.substring(n-s.length(),j+max));  
   return reverse? reverse(str.substring(n-s.length(),j+max)):str.substring(n-s.length(),j+max);  
 }  
 public static String reverse(String s){  
       StringBuilder sb = new StringBuilder();  
    for(int i = s.length()-1; i>=0; i--)  
      sb.append(s.charAt(i));  
    return sb.toString();  
 }