文字列内の各サフィックスの発生数を調べるにはどうすればよいですか？

Question

オリジナルの文字列内で、文字列の各接尾辞が何回出現するかをO（nlogn）またはO（n）の時間で検索したいと考えています。

たとえば、文字列abaの場合、接尾辞aが2回​​表示され、baが一度表示され、abaが一度表示されます。

Answer 1

接尾辞配列ソリューション

LCP配列と一緒に、文字列Sの構築物の接尾辞木。これは、各接尾辞のすべての出現を数えるのに役立ちます。

サフィックス配列とLCPが何であるかを知ることなく、その理解が困難です。

suffix array

LCP

kasai’s Algorithm for Construction of LCP array from Suffix Array

私たちは例の文字列を取り、その接尾辞配列を作成してみましょう。文字列S = "ABABBAABB"を考えてみましょう。

suffix positions(pos) Suffixes of S LCP array of S 
    5     AABB   1 
    0     ABABBAABB  2 
    6     ABB    3 
    2     ABBAABB   0 
    8     B    1 
    4     BAABB   2 
    1     BABBAABB  1 
    3     BBAABB   2 
    7     BB    not Defined 

第1の列（POSアレイ）は、接尾辞配列でソートサフィックスの元の出発点です。 2番目の列をSuffixArrayと呼びましょう（視覚化のために計算する必要はありません）。

LCP [i] = SuffixArray [i]とSuffixArray [i + 1]の間の最長共通接頭語の長さを知っているように。例えばLCP 1 = lcp（ "ABABBAABB"、 "ABB"）= 2。

Let Count [i] =位置iで始まる接尾辞の出現回数を表します。

for (int i = 0; i < n;) 
{ 
    int j=i; 
    while(LCP[j]==n-pos[j]){ // loop if SuffixArray[j] is a prefix of SuffixArray[j+1] 
     j++; 
    } 
    int incr=1; 
    for (int k = j-1; k>= i ; --k) 
    { 
     count[ pos[k] ] = incr; 
     incr++; 
    } 
    i=j+1; 
} 

これは、高度に最適化されたソリューションであり、あなたはすべてのステップに向けて密接に見れば、複雑さは、O（nはn個のログ）です。

希望します。あなたが最初の試しで理解していない場合は、すべてをもう一度見てください。

---

EDIT：カウント配列のこの計算では小さなバグがあります。基本的に私の問題は、現在の値よりも小さいLCP配列の直後のインデックスを見つけることです。私は正しい実装を提供しています。

stack<int> stack; 

count[ pos[n-1] ] = 1; 

for(int i=n-2;i>=0;i--){ 
    while(!stack.empty() and LCP[stack.top()]>=LCS[i]){ 
     stack.pop(); 
    } 

    if(LCP[i] == n-pos[i] ){ 
     if (stack.empty()) 
     { 
      count[ pos[i] ] = n-i ; 
     }else{ 
      count[ pos[i] ] = stack.top()-i ; 
     } 

    }else{ 
     count[ pos[i] ] = 1; 
    } 

    stack.push(i); 

} 

next smaller element in array

---