Find longest run of a letter in a string

Write a function that returns the longest run of a letter in a string. e.g. cccc in the string abccccdef.

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: