使用后缀数组搜索后缀

Question

我已经构造了一个后缀数组，它是由一个ArrayList实现的。

我想用这个列表在后缀数组中搜索一个后缀。为此，我对列表进行了排序并使用了二进制搜索，但是 "search" 函数一直返回 -1

我不知道我做错了什么。我也覆盖了 Hashcode 和 equals。

我也更改了 "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);

使用后缀数组搜索后缀

Searching suffixes using a suffix array

java

arraylist

binary-search

comparator

suffix-array