Поиск суффиксов с использованием суффиксного массива

Question

Я построил массив суффикса, который реализован ArrayList.

Я хочу использовать этот список для поиска суффикса в массиве суффикса. Для этого я отсортировал список и использовал бинарный поиск, но функция «поиска» продолжает возвращаться -1

Я не знаю, что я делаю неправильно здесь. Я переопределил Hashcode и равный.

Я также изменил определение по умолчанию, «равно», но все же я получаю тот же результат

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.Comparator; 
import java.util.List; 

public class SuffixArrayNaive { 


/** 
* This class represents the elements in the suffix array with their respective 
* locations 
* @author Aneesh 
* 
*/ 
private class Elements implements Comparator<Elements>{ 
    String value; 
    int position; 

    public Elements() { 
     // TODO Auto-generated constructor stub 
    } 
    public Elements(String value, int position) { 
     //super(); 
     this.value = value; 
     this.position = position; 
    } 

    @Override 
    public int hashCode() { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + getOuterType().hashCode(); 
     result = prime * result + position; 
     result = prime * result + ((value == null) ? 0 : value.hashCode()); 
     return result; 
    } 

    @Override 
    public boolean equals(Object obj) { 
     if (this == obj) 
      return true; 
     if (obj == null) 
      return false; 
     Elements other = (Elements) obj; 
     if (!getOuterType().equals(other.getOuterType())) 
      return false; 
     if (value == null) { 
      if (other.value != null) 
       return false; 
     } else if (!value.equals(other.value)) 
      return false; 
     return true; 
    } 

    private SuffixArrayNaive getOuterType() { 
     return SuffixArrayNaive.this; 
    } 

    @Override 
    public int compare(Elements o1, Elements o2) { 
     // TODO Auto-generated method stub 
     if (o1.value.compareTo(o2.value)>0){ 
      return 1; 
     } 
     if (o1.value.compareTo(o2.value)<0){ 
      return -1; 
     } 
     return 0; 
    } 
    @Override 
    public String toString() { 
     return "value=" + value + ", position=" + position + "\n"; 
    } 
} 

List<Elements> suffixArray = new ArrayList<>(); 

public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    String baseString="banana"; 
    new SuffixArrayNaive().buildSuffixArray(baseString); 
    String query="na"; 
    new SuffixArrayNaive().search(query); 
} 


private int search(String query) { 
    // TODO Auto-generated method stub 
    int result = -1; 
    int res = Collections.binarySearch(suffixArray, new Elements(query, -1), new Elements()); 
    //printing -1 always!! 
    //what is wrong? 
    System.out.println(res); 
    result = res; 
    return result; 
} 

private void buildSuffixArray(String baseString) { 
    // TODO Auto-generated method stub 
    //generate all suffixes of the baseString 
    int length= baseString.length(); 

    for (int i=0;i<length;++i){ 
     suffixArray.add(new Elements(baseString.substring(i), i)); 
    } 

    Collections.sort(suffixArray, new Elements()); 
} 
} 

Answer 1

Выпуск находится здесь:

new SuffixArrayNaive().buildSuffixArray(baseString); 
String query="na"; 
new SuffixArrayNaive().search(query); 

В одном из Объекта SuffixArrayNaive, вы создаете suffix array (путем заполнения списка) при поиске в другом экземпляре SuffixArrayNaive, array (list), который пуст.

Помните свой список, это определить как не статики:

List<Elements> suffixArray = new ArrayList<>(); 

Значение вы будете иметь один список, связанный с каждым объектом, который вы создаете с новым ключевым словом, и это было бы пустым, при создании объекта.

Вы можете решить эту проблему путем создания массива суффиксов в одном объекте и поиска в том же объекте, где соорудили массив суффиксов:

SuffixArrayNaive suffixArrayNaive = new SuffixArrayNaive(); 
suffixArrayNaive.buildSuffixArray(baseString); 
String query="na"; 
suffixArrayNaive.search(query);