Answer:
O(n) solution which sweeps thru the array..
cur next
| |
accccefgggggg
GetRepSeq(const char* str, char **start, size_t *len)
{
const char* next = str + 1;
const char* cur = str;
size_t cur_len = 1;
*start = 0;
*len = 1;
while (*next)
{
if ( *next == *cur )
{
++next;
++cur_len;
}
else
{
/* we just encountered a non equal char */
if ( cur_len >= *len )
{
*len = cur_len;
*start = cur;
}
cur = next;
++next;
}
}
}
Alternative Answer : Sufix trees
No comments:
Post a Comment