Суффикс-массив, обозначающий внутренние узлы

Question

Зная внутренние узлы, полезно в дереве суффиксов, так как они могут помочь вам решить такие проблемы, как поиск самой длинной повторяющейся подстроки.

Их трудно построить на месте (подумайте о доске). Поэтому люди сказали мне заглянуть в массивы суффиксов.

У меня есть две части вопроса:

1. Вы можете создать массив суффиксов без создания суффикса дерева первым? Из того, что я видел, большинство реализаций строят trie, а затем пересекают его, чтобы создать массив суффикса.

2. Учитывая массив суффикса, как определить внутренние узлы?

Answer 1

(На мой взгляд, это было бы чрезвычайно сложный вопрос для доски интервью ...)

Чтобы ответить на часть 1, да это возможно (и обычно), чтобы построить массив суффиксов непосредственно.

Это link to stanford.edu дает короткий O (Nlog^2n) алгоритм, который прост в реализации:

#include <cstdio> 
#include <cstring> 
#include <algorithm> using namespace std; 
#define MAXN 65536 
#define MAXLG 17 
char A[MAXN]; 
struct entry { int nr[2], p; 
} L[MAXN]; 
int P[MAXLG][MAXN], N, i, stp, cnt; 
int cmp(struct entry a, struct entry b) 
{ 
    return a.nr[0] == b.nr[0] ? (a.nr[1] < b.nr[1] ? 1 : 0) : (a.nr[0] < b.nr[0] ? 1 : 0); 
} 
int main(void) 
{ 
    gets(A); for (N = strlen(A), i = 0; i < N; i ++) 
    P[0][i] = A[i] - 'a'; 
    for (stp = 1, cnt = 1; cnt >> 1 < N; stp ++, cnt <<= 1) { 
    for (i = 0; i < N; i ++) 
     { L[i].nr[0] = P[stp - 1][i]; 
     L[i].nr[1] = i + cnt < N ? P[stp - 1][i + cnt] : -1; 
     L[i].p = i; } 
    sort(L, L + N, cmp); 
    for (i = 0; i < N; i ++) P[stp][L[i].p] = i > 0 && L[i].nr[0] == L[i - 1].nr[0] && L[i].nr[1] == L[i - 1].nr[1] ? 
    P[stp][L[i - 1].p] : i; 
    } return 0; 
} 

Этот PDF также обсуждает, как использовать суффикс массивов в практических примерах.

В качестве альтернативы, этот 2005 paper "Linear Work Suffix Array Construction" дает подход O (n) для построения массивов суффиксов с 50 строками кода.

В моих экспериментах по строке длиной 100 тыс. Я нашел дерево суффиксов (используя алгоритм O (n) Ukkonen), чтобы занять 16 секунд, массив суффикса O (nlog^2n) займет 2,4 секунды, а O (n) массива суффиксов на 0,5 секунды.