(ALGORITMA) Turbo Boyer-Moore (part2)

Sesuai postingan tentang algoritma Turbo Boyer-Moore sebelumnya, kali ini kita akan membahas bagian koding dari algoritma ini. Nah berikut ini adalah koding dari algoritma Turbo Boyer-Moore dalam JAVA :

---

import java.util.ArrayList;
import java.util.List;

public class TBM
{
  private int m;
  private int[] bmGs;
  private int[] bmBc;
  private char[] x;

  private static void preBmBc(char[] x, int[] bmBc)
  {
    int m = x.length;

    for (int i = 0; i < bmBc.length; i++)
      bmBc[i] = m;
    for (i = 0; i < m - 1; i++)
      bmBc[x[i]] = (m - i - 1);
  }

  private static void suffixes(char[] x, int[] suff) {
    int f = 0; int m = x.length;

    suff[(m - 1)] = m;
    int g = m - 1;
    for (int i = m - 2; i >= 0; i--)
      if ((i > g) && (suff[(i + m - 1 - f)] < i - g)) {
        suff[i] = suff[(i + m - 1 - f)];
      } else {
        if (i < g)
          g = i;
        f = i;
        while ((g >= 0) && (x[g] == x[(g + m - 1 - f)]))
          g--;
        suff[i] = (f - g);
      }
  }

  private static void preBmGs(char[] x, int[] bmGs)
  {
    int m = x.length;
    int[] suff = new int[m];

    suffixes(x, suff);

    for (int i = 0; i < m; i++)
      bmGs[i] = m;
    int j = 0;
    for (i = m - 1; i >= 0; i--)
      if (suff[i] == i + 1)
        for (; j < m - 1 - i; j++)
          if (bmGs[j] == m)
            bmGs[j] = (m - 1 - i);
    for (i = 0; i <= m - 2; i++)
      bmGs[(m - 1 - suff[i])] = (m - 1 - i);
  }

  public static List findAll(String pattern, String source) {
    char[] x = pattern.toCharArray(); char[] y = source.toCharArray();
    int m = x.length; int n = y.length;
    List result = new ArrayList();

    int[] bmGs = new int[m];
    int[] bmBc = new int[65536];

    preBmGs(x, bmGs);
    preBmBc(x, bmBc);
    int u;
    int j = u = 0;
    int shift = m;
    while (j <= n - m) {
      int i = m - 1;
      while ((i >= 0) && (x[i] == y[(i + j)])) {
        i--;
        if ((u != 0) && (i == m - 1 - shift))
          i -= u;
      }
      if (i < 0) {
        result.add(Integer.valueOf(j));
        shift = bmGs[0];
        u = m - shift;
      } else {
        int v = m - 1 - i;
        int turboShift = u - v;
        int bcShift = bmBc[y[(i + j)]] - m + 1 + i;
        shift = Math.max(turboShift, bcShift);
        shift = Math.max(shift, bmGs[i]);
        if (shift == bmGs[i]) {
          u = Math.min(m - shift, v);
        } else {
          if (turboShift < bcShift)
            shift = Math.max(shift, u + 1);
          u = 0;
        }
      }
      j += shift;
    }

    return result;
  }

  public static TBM compile(String pattern) {
    char[] x = pattern.toCharArray();
    int m = x.length;

    int[] bmGs = new int[m];
    int[] bmBc = new int[65536];

    preBmGs(x, bmGs);
    preBmBc(x, bmBc);

    TBM tbm = new TBM();
    tbm.m = m;
    tbm.bmBc = bmBc;
    tbm.bmGs = bmGs;
    tbm.x = x;

    return tbm;
  }

  public List findAll(String source) {
    char[] y = source.toCharArray();
    int n = y.length;
    List result = new ArrayList();
    int u;
    int j = u = 0;
    int shift = this.m;
    while (j <= n - this.m) {
      int i = this.m - 1;
      while ((i >= 0) && (this.x[i] == y[(i + j)])) {
        i--;
        if ((u != 0) && (i == this.m - 1 - shift))
          i -= u;
      }
      if (i < 0) {
        result.add(Integer.valueOf(j));
        shift = this.bmGs[0];
        u = this.m - shift;
      } else {
        int v = this.m - 1 - i;
        int turboShift = u - v;
        int bcShift = this.bmBc[y[(i + j)]] - this.m + 1 + i;
        shift = Math.max(turboShift, bcShift);
        shift = Math.max(shift, this.bmGs[i]);
        if (shift == this.bmGs[i]) {
          u = Math.min(this.m - shift, v);
        } else {
          if (turboShift < bcShift)
            shift = Math.max(shift, u + 1);
          u = 0;
        }
      }
      j += shift;
    }

    return result;
  }
}

---

Untuk implementasinya dalam program, silahkan dicoba sendiri dirumah masing-masing.
Enjoy.. (^_^)v