Сопоставление с шаблоном java для первого появления шаблона s в дереве суффиксов для реализации алгоритма Укконена Марком Нельсоном

Question

Я попытался построить дерево суффиксов на основе реализации алгоритма Укконена Марком Нельсоном в коде Java, который является вариантом кода по адресу: http://www.sanfoundry.com/java-program-implement-suffix-tree/

Следующий код создает компактное дерево суффиксов (trie сжатого суффикса) из сканирования текстового файла, содержащего слово "минимум", расположенное в текстовом файле следующим образом:

min
im
ize    

Дерево суффиксов сжимается в форму списка массивов на основе алгоритма Укконена с использованием сжатия Edge-Label, так что на все суффиксы можно ссылаться из индекса представления одного массива.

Код также распечатывает все содержимое и детали дерева суффиксов следующим образом:

Start  End  Suf  First Last  String

  0    10  -1     7      7   e
  0     4   0     1      1   i
  0     6   4     0      1   mi
  0     3  -1     2      7   nimize
  0     9  -1     6      7   ze
  4     5  -1     4      7   mize
  4     2  -1     2      7   nimize
  4     8  -1     6      7   ze
  6     1  -1     2      7   nimize
  6     7  -1     6      7   ze

Я использовал следующий конструктор, измененный по сравнению с текущим конструктором в Java-коде Марка Нельсона для его Java-реализации алгоритма Укконена по ссылке выше, но остальная часть его кода остается неизменной:

    public CompressedSuffixTrie(String f) // Create a compact compressed suffix trie from file f
{
    Edges = new Edge[ HASH_TABLE_SIZE ];
    for (int i = 0; i < HASH_TABLE_SIZE; i++)
        Edges[i] = new Edge();
    Nodes = new Node[ MAX_LENGTH * 2 ];
    for (int i = 0; i < MAX_LENGTH * 2 ; i++)
        Nodes[i] = new Node();
    active = new Suffix( 0, 0, -1 );

    // Create new Scanner to scan file
    Scanner s;
    try {
        s = new Scanner(new File(f + ".txt"));

        // ArrayList to be converted into String
        ArrayList<String> arraylist = new ArrayList<String>();
        // Add every line of text containing sequence from file f into ArrayList
        while (s.hasNextLine()){
            arraylist.add(s.nextLine());
        }
        s.close();

        // Convert ArrayList to String using advanced for-each loop and StringBuilder
        StringBuilder sb = new StringBuilder();
        for (String str : arraylist) {
            sb.append(str); // append contents to StringBuilder
        }
        String str = sb.toString(); // convert back to String

        /** Construct Suffix Tree **/       
        this.T = str.toCharArray();
        this.N = this.T.length - 1;  

        for (int i = 0 ; i <= this.N ; i++ )
            this.AddPrefix( this.active, i );
        this.dump_edges( this.N );      

    } catch (FileNotFoundException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }

}

Кажется, код работает правильно, но я хочу найти первое вхождение шаблона s в дереве суффиксов, которое возвращает начальный индекс первого вхождения шаблона s. Например, если s появляется в дереве суффиксов, findString(s) вернет начальный индекс первого вхождения s в дереве суффиксов. В противном случае он вернет -1.

Есть ли способ сделать это так, чтобы метод findString(s) не медленнее, чем сложность времени O(|s|), где | s | длина с?

Answer 1

Если вы говорите о синтаксическом анализе вывода суффиксного дерева печати, то это должно вернуть каждый элемент, который не имеет -1 под Suf колонка:

(\n?)\s+\d+\s+\d+\s+(?!-1)([\d-]+)\s+\d+\s+\d+\s+(\w+)(\n?)

Группа 2 имеет индекс, а группа 3 - суффикс.

Если вы не говорите о синтаксическом анализе печатного вывода, тогда вопрос на самом деле не в регулярном выражении или сопоставлении с образцом, а в том, как разобраться в этом.