tioj 1515 似曾相識

首先要先對名詞有點概念：

1. suffix：hello, ello, llo, lo, o 皆為hello的後綴
2. sa[i]（後綴數組）：問某個名次是第幾個後綴
3. ra[i]（排名數組）：問某個後綴是第幾名
4. lcp( i, j ) ： 問第 i 個後綴與第 j 個後綴的最長共同前綴
5. LCP( i, j ) ： 問第 i 名與第 j 名的最長共同前綴
6. height[i] : 問第 i 名跟第 i -1 名的最長共同前綴
7. h[i] : 問第 i 個後綴與排在第 i 個後綴前一名最長共同前綴

大致記一記之後，就要進入演算法的部份了。

1.  SA_MAKER ( Doubling Algorithm ): 

          概念：當你有某字串的前半排名與後半排名，你便可以得到他的排名。故你先一次求得每單一字母的排名（用Counting），接著用一變二，二變四，四變八...，logn快速求得，故他稱為doubling algorithm。

          實作：

int ws[MAXN], wv[MAXN], wa[MAXN], wb[MAXN];
bool cmp( int *r, int a, int b, int l, int n )
{ return r[a] == r[b] && r[a+l] == r[b+l]; }
void SA_maker( char* str, int* sa, int n, int m ){
int i, p = 0, *x = wa, *y = wb;
      for( i = 0 ; i < m ; i++ ) ws[i] = 0;
for( i = 0 ; i < n ; i++ ) ws[ (x[i] = (int)str[i]) ]++;
for( i = 1 ; i < m ; i++ ) ws[i] += ws[i-1];
for( i = 0 ; i < n ; i++ ) sa[ --ws[x[i]] ] = i;
for( int l = 1 ; p < n ; l*=2, m = p ){
// sort the second element
              for( i = n-l, p = 0 ; i < n ; i++ ) y[p++] = i;
for( i = 0 ; i < n ; i++ ) if( sa[i] >= l ) y[p++] = sa[i]-l;
for( i = 0 ; i < n ; i++ ) wv[i] = x[y[i]];
              // sort the first element 
              for( i = 0 ; i < m ; i++ ) ws[i] = 0;
for( i = 0 ; i < n ; i++ ) ws[wv[i]]++;
for( i = 1 ; i < m ; i++ ) ws[i] += ws[i-1];
for( i = n-1 ; i >= 0 ; i-- ) sa[ --ws[wv[i]] ] = y[i];
              // Get value 
              swap( x, y ); x[sa[0]] = 0;
for( i = 1, p = 1 ; i < n ; i++ )
                    x[sa[i]] = cmp( y, sa[i], sa[i-1], l, n ) ? p-1 : p++ ;
}
}

Reference:


         m：排名值的最大值+1         sa[i]=j：第 i 名是第 j 個後綴
         x[i]=j：第 i 個後綴的排名值
         y[i]=j：第 i 名是第 j 個後綴（照第二元素排名）
         ws[i]=j：第 i 個值的最後一個排名＋1 = j
         wv[i]=j：第 i 名的先前排名值（照第二元素排名）


講解：


     ！這個函數有使用限制， s 的最後一個元素必須為零！
             （也就是得到的sa數組要從第1個數起）
       

        為了使每個logn裡之要花費 n 的時間，這邊使用的是Radix Sort，而且是不太一樣的Radix Sort，本來我寫的是用Vector做的Radix Sort，因為用Vector，速度極慢，這種寫法是在網路上東看西看發現的。

        首先先得到一個個字母的排序，存在 sa[] 當中。ws[]是用來存當前的某個數值的名次。x[] 是存此位置的ranking相對值。（並非絕對的1, 2, 3, 4...，而是像1, 2, 5, 12之類的）


        接下來就進入doubling的步驟：1. 排序第二元素，第一迴圈（超出去的就直接是最大的），第二迴圈（剩下的就跟sa值一樣），第三迴圈（方便之後使用）2. 排序第一元素（最終排序），此時作法與外頭對單一字母排序的方法類似，唯一差別在於要從後面開始放進來，因為y[i]是以排序過的。而且排名是從大的開是進來（--ws[wv[i]] ）。3. 得到排名值，如果一樣的話排名值相同，他使用的cmp是特製過的，他看起來會取到不該取的值，但是因為最後一個值是零，所以如果兩個相等的話，他不會超過最後一個值。


2.  H_maker（LCP Theorem）:


       定理1：LCP( i, j ) = min{ LCP( k-1, k ), i+1~j }
       定理2：h[i] >= h[i-1]-1，當 i > 1且 ra[i] > 1
                           證明困難，實作簡單。
       實作：

int sa[MAXN], ra[MAXN];
void H_maker( char *s, int *h, int n ){
SA_maker( s, sa, n+1, 128 );
for( int i = 1 ; i <= n ; i++ ) ra[sa[i]] = i;
for( int i = 1 ; i <= n ; i++ ){
if( ra[i] == 0 ){ h[i] = 0; continue; }
if( i == 0 || h[i-1] <= 1 ) h[i] = 0;
else h[i] = h[i-1]-1;
int x = sa[ra[i]-1], y = sa[ra[i]];
while( max(x,y)+h[i] < n && s[x+h[i]] == s[y+h[i]] ) h[i]++;
}
}