codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
int *rk = new int[N], *kr = new int[N], cnt[N]; void SA( int sa[], int ra[], char s[] ){ int n = strlen(s), m = 128, l, h, i, j; for( i=j=0; i<=n; i++ ) rk[i]=s[sa[i]=i]; for( l=1,h=0; j<=n; l<<=1 ){ for( i=n-h,j=0; i<n; i++ ) kr[j++]=i; for( i=0; i<n; i++ ) if( sa[i]>=h ) kr[j++]=sa[i]-h; for( i=0; i<m; i++ ) cnt[i]=0; for( i=0; i<n; i++ ) cnt[rk[i]]++; for( i=1; i<m; i++ ) cnt[i]+=cnt[i-1]; for( i=n-1; i>=0; i-- ) sa[--cnt[rk[kr[i]]]] =kr[i]; for( i=0,j=1; i<n; i++ ) kr[sa[i]]=(rk[sa[i]]==rk[sa[i+1]]&&rk[sa[i]+h]==rk[sa[i+1]+h])?j:j++; h=l; m=j; swap( rk, kr ); }for( i=0; i<n; i++ ) ra[sa[i]]=i; } int sa[N], ra[N], h[N], spa[30][N]; void INIT( char s[] ){ int n=strlen(s), i, j, l; SA( sa, ra, s ); for( i=0; i<n; i++ ){ if( ra[i]==0 ){ h[i]=0; continue; } h[i]=(i==0||h[i-1]<=1)?0:h[i-1]-1; int p=sa[ra[i]-1], q=i, mx=p; if(mx<q)mx=q; while( mx+h[i]<n && s[p+h[i]]==s[q+h[i]] )h[i]++; }for( i=0; i<n; i++ ) spa[0][i]=h[sa[i]]; for( i=1; i<23; i++ ) for( j=0,l=1<<i; j<n-l+1; j++ ) spa[i][j]=min(spa[i-1][j],spa[i-1][j+l/2]); } int LCP( int i, int j ){ if( i>j ) swap(i,j); i++;int l = __lg(j-i+1); return min( spa[l][i], spa[l][j-(1<<l)+1] ); }
Private
[
?
]
Run code
Submit