SHARE
TWEET

Untitled

a guest Sep 23rd, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // LCS com Bit-paralelo
  2. //https://www.spoj.com/problems/LCS0/
  3. #include <stdio.h>
  4. #include <limits.h>
  5. #include <stdlib.h>
  6. #define INF INT_MAX
  7.  
  8. char A[50002], B[50002];
  9.  
  10. int main(){
  11.     scanf("%s\n%s",A,B);
  12.     register int i, j, k, m, n;
  13.     for ( m = 0; A[m]; ++m) ;
  14.     for ( n = 0; B[n]; ++n) ;
  15.     if ( m == 0 || n == 0) return 0;
  16.     char *X = A, *Y = B;
  17.     if (m < n) {
  18.         char *T;
  19.         T = X ; X = Y ; Y = T ;
  20.         k = m ; m = n ; n = k ;
  21.     }
  22.  
  23.     int w =( m + 31) >> 5; // ceil [m /32]
  24.  
  25.     unsigned int S [256][ w ]; // Sigma {all char }
  26.     for ( i = 0; i < 256; ++i)
  27.     for ( j = 0; j < w ; ++j)
  28.     S [ i ][ j ]=0;
  29.  
  30.     unsigned int set = 1;
  31.     for ( i = 0 , j = 0; i < m ; ++i) {
  32.         S [ X [ i ]][ j ] |= set ;
  33.         set <<= 1;
  34.         if (!set) { ++set; ++j;}
  35.     }
  36.  
  37.     unsigned int L[w]; // Vetor L(i)
  38.     unsigned int b1 , b2 , c ; // borrows and carries
  39.  
  40.     for ( i = 0; i < w ; ++i) L[i] = 0;
  41.  
  42.     register unsigned int U, V;
  43.     for ( i =0; i < n ; ++i) {
  44.         b1 = 1; b2 = 0;
  45.         for ( j = 0; j < w ; ++j) {
  46.             U = L[j] | S [ Y[i] ][j];
  47.             c = L[j] >> 31;
  48.             V = U - ( L[j] << 1 | b1 + b2 ) ;
  49.             b1 = c; b2 = ( V > U ) ;
  50.             L[j] = U & (~V) ;
  51.         }
  52.     }
  53.     for ( k = 0 , i = 0; i < w ; ++i)
  54.         for (; L [ i ]; ++k) L[i] &= L[i] - 1;
  55.     printf("%d\n", k);
  56.  }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top