public class GraphOracle {
private NodeOracle[] nodes;
private int size;
private String pattern;
private String currentWord;
public GraphOracle(String pattern){
size = pattern.length()+1;
this.pattern = pattern;
nodes = new NodeOracle[size];
for(int i=0; i<size; i++)nodes[i] = new NodeOracle();
}
public void Oracle(){
for(int i=0; i<size-1; i++)
{
currentWord = pattern.substring(i, i+1);
//añadimos la transición (i) ----(pattern[i])---> (i+1)
nodes[i].putTransition(new Transition(i, i+1, currentWord));
recursiveOracle(i, i+1);
}
}
private void recursiveOracle(int i, int nodoActual){
//miramos el suffix-link a no ser que sea el nodo inicial,
//si lo es hacemos que apunte a él
if(i==0) nodes[nodoActual].setLink(nodoActual, 0);
//si no es el nodo inicial seguimos el suffix-link del nodes[i]
else{
//cogemos el Nodo destino del suffix link de nodes[i]
int linkEnd = nodes[i].getLinkEnd();
//si el nodo destino del suffix-link de nodes[i] tenía
//alguna transición con currentWord actualizamos nuestro
//suffix-link haciendo que el nodo actual apunte al
//destino de dicha transición
int nodoDestino = nodes[linkEnd].hasTransition(currentWord);
if (nodoDestino>-1) //Existe una transición con currentWord
nodes[nodoActual].setLink(nodoActual, nodoDestino);
else{
//añadimos la transición hacia nosotros
nodes[linkEnd].putTransition(
new Transition(linkEnd, nodoActual, currentWord));
recursiveOracle(linkEnd, nodoActual);
}
}
}
}
public class NodeOracle {
private ArrayList transitions;
private Transition link;
public NodeOracle(){
transitions = new ArrayList();
link = new Transition();
}
public void putTransition(Transition t){transitions.add(t);}
public void setLink(int start,int end){
link.setValues(start,end,"");}
public int getLinkEnd(){return link.getEnd();}
/** Comprueba si existe alguna transición con actual y retorna
* el número de nodo que recibe dicha transición. */
public int hasTransition(String actual){
for(int i=0; i<transitions.size(); i++)
{
Transition t = (Transition)(transitions.get(i));
if (t.getWord().equals(actual)) return t.getEnd();
}
return -1;
}
}
public class Transition {
private int start;
private int end;
private String word;
public Transition() {
start = -1;
end = -1;
word = "";
}
public Transition(int start, int end, String word) {
this.start = start;
this.end = end;
this.word = word;
}
public void setValues(int start, int end, String word){
this.start = start;
this.end = end;
this.word = word;
}
public int getEnd(){return this.end;}
public String getWord(){return this.word;}
}