Advertisement
Guest User

Untitled

a guest
May 25th, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 1.00 KB | None | 0 0
  1.     public static int [] computeLastOccurence (String pattern, String alphabet) {
  2.         int m = pattern.length();
  3.         int l = alphabet.length();
  4.         int [] lambda = new int [l];
  5.  
  6.         for (int i = 0; i < l; i++)
  7.             lambda[i] = m;
  8.        
  9.         for (int j = 0; j <= m-2; j++)
  10.             lambda[alphabet.indexOf(pattern.charAt(j))] = m-1-j;
  11.        
  12.         return lambda;
  13.     }
  14.  
  15.     public static void match (String text, String pattern, String alphabet) {
  16.         int n = text.length();
  17.         int m = pattern.length();
  18.         int [] lambda = BMHMatcher.computeLastOccurence (pattern, alphabet);
  19.  
  20.         int s = 0;
  21.         int j;
  22.  
  23.         while (s <= n-m) {
  24.             j = m-1;
  25.  
  26.             while (j >= 0 && pattern.charAt(j) == text.charAt(j)) {
  27.                 j--;
  28.             }
  29.  
  30.             if (j == -1)
  31.                 System.out.println("Pattern occurrs with shift " + s);
  32.  
  33.             s += lambda[alphabet.indexOf(text.charAt(s+m-1))];
  34.         }
  35.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement