I'm supposed to write a program that will search for longest common substrings in two strings of DNA. Our hint was to look on wikipedia (http://en.wikipedia.org/wiki/Longest_common_substring_problem#Dynamic_programming). I did that and I understand the principle of comparing two strings.
I'm currently facing two problems. First one is array allocation. When I find first common substring which has at least 2 characters, I dynamically allocate memory using malloc.
res = (char **) malloc(1 * sizeof (char*));
for (i = 0; i < 1; i++) {
L[i] = (char *) malloc(z * sizeof (char));
}(where z is the length of the substring)
I'm using two dimensional array because if I find another substring of the same length, I need to add it to the same array. And that's where my problem is - I don't know how to add another line to the array without deleting what's already inside. I know I need to use realloc somehow, but I don't know how to use it with two dimenional array.
My other problem are multiplicities. If I find substring of the same length as the previous ones, I automatically add it to the array without checking whether it's not equal to some other substring already in the array.
Now I understand that checking for multiplicities in the array is rather complicated and it takes a lot of time and memory. Could it be done before I actually add the string to the array?
Sorry for my english, I've been learning only for a few years :)