# CIPR Algorithm(bit-vector, 2001)

Main features
• Make use of word-level parallelism in order to compute the matrix L more efficiently
• The algorithm is based on the O(1)-time computation of each column in L by using a bit-parallel formula
• The Levenshtein distance is defined as the minimum number of character insertions and/or deletions required to transform a string x into a string y
• searching phase in O(nm/w) time complexity
• searching phase in O(m/w) space complexity
Description

Crochemore et al. proposed a bit-vector algorithm for the longest common subsequence(LCS) problem with four bit operations compared to the five bit operations of Allison and Dix(Allison-Dix Algorithm). The complexity of this algorithm is O(mn/w) time and O(m/w) space, where w is the word size of the machine.

C source code
```int CIPR_Alg(char *stringA, char *stringB, int m, int n)
{
int i, j, bitStringCount, LCS = 0, carry, type, in, bitDo;
char matchTable[DATATYPE] = { FLASE };
unsigned char **alphbetString, *prevRow, *tempX, temp, **revAlphbetString;

bitStringCount = (int) ceil((double) m / BITSIZE);

prevRow = (unsigned char*) calloc(bitStringCount + 1, sizeof(unsigned char));
// Init the prev. row

tempX = (unsigned char*) calloc(bitStringCount + 1, sizeof(unsigned char));
//Init temp string X

memset(prevRow, (int) pow((float) 2, DATATYPE) - 1, bitStringCount + 1);

for (i = 1; i <= m; i++){
matchTable[stringA[i]] = TRUE;
}
for (i = 1; i <= n; i++){
matchTable[stringB[i]] = TRUE;
}// Mark the used alphbet

alphbetString = (unsigned char**) calloc(DATATYPE, sizeof(unsigned char*));
revAlphbetString = (unsigned char**) calloc(DATATYPE, sizeof(unsigned char*));
// Set the size of alphbet string

for (i = 0; i <= DATATYPE; i++){
if (matchTable[i] == TRUE){
alphbetString[i] = (unsigned char*) calloc(bitStringCount + 1, sizeof(unsigned char));
revAlphbetString[i] = (unsigned char*) calloc(bitStringCount + 1, sizeof(unsigned char));
}
}// Init the size of alphbet string which are used

for (i = 0; i < bitStringCount; i++){
for (j = 1; j <= BITSIZE; j++){
if (m%BITSIZE != 0 && (i == bitStringCount - 1) && (j > m%BITSIZE)){
break;
}
alphbetString[stringA[i*BITSIZE + j]][i + 1] += (int) pow((double) 2, (int) (BITSIZE - j));
}
}// Init the value of alphbet string which are used

for (type = 0; type < DATATYPE; type++){
if (matchTable[type] == TRUE){
for (j = 1; j <= bitStringCount; j++){
for (in = 0, bitDo = 1; bitDo <= BITSIZE; bitDo++){
if (alphbetString[type][j] % 2 == 1){
in = 1;
}
alphbetString[type][j] /= 2;
revAlphbetString[type][j] *= 2;

if (in == 1){
revAlphbetString[type][j]++;
in = 0;
}
}
}
}
}
prevRow[1]++;
for (i = 1; i <= n; i++){
for (j = 1; j <= bitStringCount; j++){
tempX[j] = prevRow[j] & revAlphbetString[stringB[i]][j];

}// Process AND operation

if (m%BITSIZE != 0){
/*for (j = 1, temp = 0; j <= m%BITSIZE; j++){
temp += (int) pow((float) 2, BITSIZE - j);
}*/
temp = 1;
prevRow[bitStringCount] &= temp;
}

for (j = 1, carry = 0; j <= bitStringCount; j++){
if ((prevRow[j] + tempX[j] < (int) pow((float) 2, BITSIZE) && carry == 0) || (prevRow[j] + tempX[j] + 1 < (int) pow((float) 2, BITSIZE) && carry == 1)){
tempX[j] += prevRow[j];
if (carry == 1){
tempX[j]++;
}
carry = 0;
}
else{
tempX[j] += prevRow[j];
if (carry == 1){
tempX[j]++;
}
carry = 1;
}
}

for (j = 1; j <= bitStringCount; j++){
prevRow[j] = tempX[j] | (prevRow[j] & (((int) pow((float) 2, BITSIZE) - 1) - revAlphbetString[stringB[i]][j]));
}// Process OR operation

if (m%BITSIZE != 0){
temp = 1;
prevRow[bitStringCount] &= temp;
}
}

for (i = 1; i <= bitStringCount; i++){
for (j = 1; j <= BITSIZE; j++){
if (m%BITSIZE != 0 && (i == bitStringCount) && (j > m%BITSIZE)){
break;
}
if (prevRow[i] % 2 == 0){
LCS++;
}
prevRow[i] /= 2;
}
}// Find the LCS

free(alphbetString);
free(revAlphbetString);
free(tempX);
free(prevRow);

return LCS;
}
```
The files
main.c   lcslib.h   CIPR_Alg.exe

Reference
M. Crochemore, C. S. Iliopoulos, Y. J. Pinzon, and J. F. Reid, "A fast and practical bitvector algorithm for the longest common subsequence problem," Information Processing Letters, Vol. 80, pp. 279-285, 2001.