java - 使用后缀数组搜索后缀

Question

我构造了一个由 ArrayList 实现的后缀数组。

我想使用这个列表来搜索后缀数组中的后缀。为此，我对列表进行了排序并使用了二分搜索，但“搜索”函数始终返回 -1

我不知道我在这里做错了什么。我也重写了 Hashcode 和 equals。

我还更改了“等于”的默认定义，但我仍然得到相同的输出

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<>();

这意味着您将拥有一个与使用 new 关键字创建的每个对象关联的列表，并且在创建对象时该列表将为空。

您可以通过在一个对象中创建后缀数组并在构建后缀数组的同一对象中进行搜索来解决此问题:

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