проблема с реализацией дерева суффиксов

Question

Я изучаю некоторую реализацию дерева суффикса, и вот одна эталонная реализация, и вопрос в том, как «индексы» (см. Строку 19) используются для класса SuffixTreeNode? Я не уверен, что «индексы» полезны, и я думаю, вероятно, нам просто нужно сохранить значение всех узлов и их детей? Не найти слишком много значений «индексов» для класса SuffixTreeNode.

Пожалуйста, не стесняйтесь поправить меня. Любые идеи оцениваются.

public class SuffixTree { 
    SuffixTreeNode root = new SuffixTreeNode(); 
    public SuffixTree(String s) { 
     for (int i = 0; i < s.length(); i++) { 
      String suffix = s.substring(i); 
      root.insertString(suffix, i); 
     } 
    } 

    public ArrayList<Integer> getIndexes(String s) { 
     return root.getIndexes(s); 
    } 
} 

public class SuffixTreeNode { 
    HashMap<Character, SuffixTreeNode> children = new 
    HashMap<Character, SuffixTreeNode>(); 
    char value; 
    ArrayList<Integer> indexes = new ArrayList<Integer>(); 
    public SuffixTreeNode() { } 

    public void insertString(String s, int index) { 
     indexes.add(index); 
     if (s != null && s.length() > 0) { 
      value = s.charAt(0); 
      SuffixTreeNode child = null; 
      if (children.containsKey(value)) { 
       child = children.get(value); 
      } else { 
       child = new SuffixTreeNode(); 
       children.put(value, child); 
      } 
      String remainder = s.substring(1); 
      child.insertString(remainder, index); 
     } 
    } 

    public ArrayList<Integer> getIndexes(String s) { 
     if (s == null || s.length() == 0) { 
      return indexes; 
     } else { 
      char first = s.charAt(0); 
      if (children.containsKey(first)) { 
       String remainder = s.substring(1); 
       return children.get(first).getIndexes(remainder); 
      } 
     } 
     return null; 
    } 
} 

public class Question { 
    public static void main(String[] args) { 
     String testString = “mississippi”; 
     String[] stringList = {“is”, “sip”, “hi”, “sis”}; 
     SuffixTree tree = new SuffixTree(testString); 
     for (String s : stringList) { 
      ArrayList<Integer> list = tree.getIndexes(s); 
      if (list != null) { 
       System.out.println(s + “: “ + list.toString()); 
      } 
     } 
    } 
} 

Answer 1

indexes, безусловно, необходим для реализации вы смотрите из дерева суффиксов (есть несколько версий дерева суффиксов некоторые более эффективен, чем другие). Переменная indexes играет неотъемлемую роль в возвращении индексов, где подстрока (is, sip, hi, sis) существует в исходной строке (mississippi) обратно вызывающему методу. getIndexes возвращает indexes в своем базовом примере, как вы получаете список вхождений каждой подстроки. см. ниже выход

is: [1, 4] 
sip: [6] 
sis: [3]