
import javax.swing.JOptionPane;
public class BOM{
static int teta = 1000;//teta
static int k = teta;
static int s = teta;
static int pos = 0;
static int current = 0;
public static void main(String[] args){
String texto = JOptionPane.showInputDialog(null, "Ingrese el Texto de Entrada", "BOM", 1);//"AGATACGATATATAC";//input text
String patron = JOptionPane.showInputDialog(null, "Ingrese el Patron a Buscar", "BOM", 1);//"ATATA";//Backward pattern
//mensaje
int n = texto.length();
int m = patron.length();
int lengthAscii = 255;
int states[] = new int[m + 1];
int transitions[][] = new int[m + 1][lengthAscii];
for (int i = 0; i <= m ; i++){
states[i] = teta;
for (int j = 0; j < lengthAscii; j++){
transitions[i][j] = teta;
}
}
for (int j = 1; j <= m; j++){
oracle_add_letter(states, transitions, j - 1, patron.charAt(j - 1));
}
//searching
pos = 0;
while (pos <= n - m){
current = 0;
int j = m;
while(j > 0 && current != teta){
int textPos = Character.getNumericValue(texto.charAt(pos + j));
current = transitions[current][textPos];
j = j - 1;
}
if(current != teta){
System.out.println("El Patron Aparece en la Posicion: " + (pos + 1));
}
pos = pos + j + 1;
}
}
private static void oracle_add_letter(int[] states, int[][] transitions, int m, char sigma){
int sigmaNum = Character.getNumericValue(sigma);
transitions[m][sigmaNum] = m + 1;
k = states[m];
while (k != teta && transitions[k][sigmaNum] == teta){
transitions[k][sigmaNum] = m + 1;
k = states[k];
}
if (k == teta) s = 0;
else s = transitions[k][sigmaNum];
states[m + 1] = s;
}
}