﻿ Hirschberg C

# Hirschberg Algorithm C(Divide and Conquer, 1975)

Main features
• searching phase in O(mn) time complexity
• searching phase in O(m+n) space complexity
Description

Hirschberg proposed one quadratic space and two linear space algorithms for the longest common subsequence(LCS) of two strings. This algorithm(Algorithm C) is a devide and conquer approch. The idea is to find the intersecting point of the LCS sequence with the m/2 th row and solve the problem recursively. This algorithm solves LCS problem in O(mn) time and in O(m+n) space.

C source code
```int Hirschberg_AlgC(char *stringA, char *stringB, int m, int n)
{
int **arr, **arr2, i, j, max, arrmax, arr2max, up, down;

if (m == 1 || n == 0){
if (n == 0)
return 0;
for (j = 1; j <= n; j++){
if (stringA == stringB[j])
return 1;
}
return 0;
}

arr = (int**)calloc(2, sizeof(int*));
arr2 = (int**)calloc(2, sizeof(int*));

arrmax = m / 2;
arr2max = m - arrmax;
up = 1;
down = 0;

for (i = 0; i < 2; i++){
arr[i] = (int*)calloc((n + 1), sizeof(int));
arr2[i] = (int*)calloc((n + 1), sizeof(int));
}

/*-----fill in arr by using algB -----*/
for (i = 0; i <= arrmax; i++){
for (j = 0; j <= n; j++){
if (j == 0 || i == 0)
arr[down][j] = 0;
else{
if (stringA[i] == stringB[j]){
arr[down][j] = arr[up][j - 1] + 1;
}
else{
arr[down][j] = arr[up][j];
if (arr[down][j] < arr[down][j - 1])
arr[down][j] = arr[down][j - 1];
}
}
}
up ^= down;//swap up and down by using EXOR
down ^= up;
up ^= down;
}

arrmax = up;//remember the position of the last row

/*-----fill in arr2 by using algB -----*/
for (i = 0; i <= arr2max; i++){
for (j = 0; j <= n; j++){
if (j == 0 || i == 0)
arr2[down][j] = 0;
else{
if (stringA[m - i + 1] == stringB[n - j + 1]){
arr2[down][j] = arr2[up][j - 1] + 1;
}
else{
arr2[down][j] = arr2[up][j];
if (arr2[down][j] < arr2[down][j - 1])
arr2[down][j] = arr2[down][j - 1];
}
}
}
up ^= down;//swap up and down by using EXOR
down ^= up;
up ^= down;
}

arr2max = up;//remember the position of the last row

/*-----find k and MAX-----*/
max = 0;
j = 0;//the k is the min j that makes MAX

for (i = 0; i <= n; i++){
if (arr[arrmax][i] + arr2[arr2max][n - i] > max){
max = arr[arrmax][i] + arr2[arr2max][n - i];
j = i;
}
}

return Hirschberg_AlgC(stringA, stringB, m / 2, j) + Hirschberg_AlgC(&stringA[m / 2], &stringB[j], m - m / 2, n - j);

}
```
The files
main.c   lcslib.h   Hirschberg_AlgC.exe

Reference
D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequence," Communications of the ACM, Vol. 24, pp. 664-675, 1975.