使用後綴數組搜索後綴

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的目的之一，就是在創建後綴數組（通過填充列表）在另一個SuffixArrayNaive實例上進行搜索時，數組（列表）是空的。

記住你的列表定義爲非靜態：

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

這意味着你將與你的新關鍵字創建的所有對象相關聯的一個列表，並在創建對象時，它會是空的。

您可以通過在一個對象創建後綴數組，並在同一個對象搜索，你所建造的後綴數組解決此問題：

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