Comment trouver la sous-chaîne d'une chaîne en utilisant le suffixe array et le tableau LCP?

Question

Si nous arrangeons tous les distincts sous-chaînes d'une chaîne lexicographique et nous avons besoin du i'th

substring

1.) Est-il possible de le trouver en utilisant son suffix array et LCP array?

2.) Si oui, comment le faisons-nous? peut-il être fait en O (Nlog^N) en créant le tableau de suffixes en utilisant Manber & Myers qui a une complexité temporelle de O (Nlog^2N) ou en créant son tableau LCP en utilisant l'algorithme de kasai qui a une complexité temporelle de O (N)?

Answer 1

Oui, cela peut être fait en utilisant un tableau Suffix et un tableau LCP.

En supposant que vous savez comment calculer tableau de suffixe et tableau LCP.

Soit p[] le tableau de suffixe lcp[] indique le tableau LCP.

créer un tableau stockant le numéro de sous-chaîne distincte jusqu'à i'th suffixe de rang. Cela peut être calculé en utilisant cette formule. Pour plus de détails, voir Here

Soit cum[] désignent tableau cumulatif qui peut être calculé comme suit:

cum[0] = n - p[0]; 
for i = 1 to n do: 
    cum[i] = cum[i-1] + (n - p[i] - lcp[i]) 

maintenant pour trouver i'th chaîne de sous juste trouver la limite de i inférieure dans le tableau cumulatif cum[] cela vous donnera le rang de suffixe d'où votre sous-chaîne devrait commencer et imprimer tous les caractères jusqu'à la longueur de

i - cum[pos-1] + lcp[pos] // i lies between cum[pos-1] and cum[pos] so for finding 
          // length of sub string starting from cum[pos-1] we should 
          // subtract cum[pos-1] from i and add lcp[pos] as it is 
          // common string between current rank suffix and 
          // previous rank suffix. 

où pos est la valeur retournée par la borne inférieure.

L'ensemble du processus ci-dessus peut se résumer comme suit:

string ithSubstring(int i){ 
    pos = lower_bound(cum , cum + n , i); 
    return S.substr(arr[pos] , i - cum[pos-1] + lcp[pos]);// considering S as original character string 
} 

Pour la pleine application de la matrice Suffixe, LCP et au-dessus logique, vous pouvez voir Here