Spidey wrote:
What is best solution for finding "a repeatedly occuring lenghtiest sub
SEQUENCE from a given paragraph"
ex:
input:
hello world is a good hello world. Is that the way it is
a way.
Output:
hello world
Here's my solution...
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* Find the longest sub-sequence of src, *
* which is repeated at least once. */
char *longsubseq(const char *src)
{
size_t substrlen, offset, srclen = strlen(src);
char *substr = malloc(srclen/2 + 1), *repeat;
if(!substr) return NULL;
for(substrlen = srclen/2; substrlen > 0; substrlen--)
{
for(offset = 0; offset < srclen - substrlen; offset++)
{
substr[0] = 0;
strncat(substr, src + offset, substrlen);
repeat = strstr(src + offset + substrlen, substr);
if(repeat) return substr;
}
}
free(substr);
return NULL;
}
If there is no subsequence that is repeated at least once, it will
return a null pointer. Otherwise, it returns a pointer to allocated
memory containing a string with the longest repeated subsequence.
This uses a rather naive algorithm, certainly not the most efficient.
--
Simon.
