Acme substring

1. 题意：在string A里边找X *是wildcard character 可以match any character
返回the starting position

2.算法：
test case:
a is shorter then x

KMP

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

Examples:
For the pattern “AABAACAABAA”, lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
For the pattern “ABCDE”, lps[] is [0, 0, 0, 0, 0]
For the pattern “AAAAA”, lps[] is [0, 1, 2, 3, 4]
For the pattern “AAABAAA”, lps[] is [0, 1, 2, 0, 1, 2, 3]
For the pattern “AAACAAAAAC”, lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

Searching Algorithm:
Unlike the Naive algo where we slide the pattern by one, we use a value from lps[] to decide the next sliding position. Let us see how we do that. When we compare pat[j] with txt[i] and see a mismatch, we know that characters pat[0..j-1] match with txt[i-j+1…i-1], and we also know that lps[j-1] characters of pat[0…j-1] are both proper prefix and suffix which means we do not need to match these lps[j-1] characters with txt[i-j…i-1] because we know that these characters will anyway match.

Preprocessing Algorithm:
In the preprocessing part, we calculate values in lps[]. To do that, we keep track of the length of the longest prefix suffix value (we use len variable for this purpose) for the previous index. We initialize lps[0] and len as 0. If pat[len] and pat[i] match, we increment len by 1 and assign the incremented value to lps[i]. If pat[i] and pat[len] do not match and len is not 0, we update len to lps[len-1]. 

 public static int firstOccurrence(String a, String x){  
        int[] lps = longestPrefixSuffix(x);  
        System.out.println(Arrays.toString(lps));  
        int i = 0, j= 0;  
        while(i < a.length()){  
             System.out.println(j);  
             if(j == x.length()){  
                  return i - x.length();  
             }  
             if(a.charAt(i) == x.charAt(j) || x.charAt(j) == '*'){  
                  i++;j++;  
             }else{  
                  if(j==0)  
                       i++;  
                  else  
                       j = lps[j-1];  
             }  
        }  
        return j == x.length()? i-x.length():-1;  
      }  
      public static int[] longestPrefixSuffix(String s){  
           int len = 0;  
           int i = 1;  
           int[] lps = new int[s.length()];  
           while(i<s.length()){  
                if(s.charAt(i) == s.charAt(len) ){  
                     len++;  
                     lps[i] = len;  
                     i++;  
                }else{  
                     if(len == 0){  
                          lps[i] = len;  
                          i++;  
                     }   
                     else{  
                          len = lps[len-1];  
                     }  
                }  
           }  
           return lps;  
      }