Я создал массив суффиксов, но я не знаю, что не так с этим кодом - PullRequest
Новая
       49

Я создал массив суффиксов, но я не знаю, что не так с этим кодом

0 голосов
/ 09 июня 2018 
import java.util.Arrays;
import java.util.Scanner;

public class SuffixArray {
public static class Tuple implements Comparable<Tuple>{
    public Integer originalIndex;
    public Integer firstHalf;
    public Integer secondHalf;
@Override
    public int compareTo(Tuple o) {
        if(this.firstHalf.compareTo(o.firstHalf)==0){
            return this.secondHalf.compareTo(o.secondHalf);
        }else {
            return this.firstHalf.compareTo(o.firstHalf);
        }
    }
}
public static void main(String args[]){
    Scanner scanner = new Scanner(System.in);
    String input = scanner.next();
    int n = input.length();
    Tuple[] tuples = new Tuple[n];
    int[][] suffixRank = new int[100][100];
    for (int i = 0; i < n; i++){
        tuples[i] = new Tuple();
        suffixRank[0][i] = input.charAt(i) - 'a';
    }
    for(int step=1, count=1;count < n;count*=2, step++){
        for (int i = 0; i<n;i++){
            tuples[i].firstHalf = suffixRank[step-1][i];
            tuples[i].secondHalf = i + count < n ? suffixRank[step-1][i+count] : -1;
            tuples[i].originalIndex = i;
        }
        Arrays.sort(tuples);
        for (int i=0;i<n;i++){
            suffixRank[step][tuples[i].originalIndex] = i > 0 && tuples[i].firstHalf == tuples[i-1].firstHalf && tuples[i].secondHalf==tuples[i-1].secondHalf ? suffixRank[step][tuples[i].originalIndex] : i;
        }
    }
    for (int i=0;i<n;i++){
        System.out.print(tuples[i].originalIndex + " ");
    }
  }
}

Вышеуказанная программа представляет собой массив суффиксов, использующий алгоритм nlogn.Я применил тот же алгоритм из ресурса, ссылка на который размещена ниже.Если я применяю тот же алгоритм в C ++, он работает нормально, но когда я применяю тот же код в Java, он дает неправильный вывод.Это дает мне неправильный индекс кортежей.Я не могу понять, что не так с этим кодом, поэтому, пожалуйста, помогите мне.

Суффиксный массив

контрольный пример 1:

Ввод: abaab Вывод: 3 2 0 4 1 Ожидаемый результат: 2 3 0 4 1

контрольный пример 2:

Вход: банан Выход: 4 5 3 1 0 2 Ожидаемый результат: 5 3 1 0 4 2

1 Ответ

0 голосов
/ 11 июня 2018

Не знаю, если это единственная проблема с кодом, но небольшая неточность появляется в цикле for после сортировки.В частности, после предложения if в цикле вы должны поменять 

? suffixRank[step][tuples[i].originalIndex] : i;

на следующее: 

? suffixRank[step][tuples[i-1].originalIndex] : i;
...