2012年4月20日 星期五

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]++;
}
}



       

4 則留言: