that's right, it has worst case quadratic time complexity.
W Karas wrote:
> aj wrote:
> > linear worst case time.
>
> The best I can do is:
>
> bool is_palin(const char x[], unsigned len)
> {
> if (len < 2)
> return(true);
> for (unsigned i = 0, j = len - 1; i < j; i++, j--)
> if (x[i] != x[j])
> return(false);
> return(true);
> }
>
> unsigned prefix_palin(const char x[], unsigned len)
> {
> unsigned i;
>
> if (len < 2)
> return(len);
>
> i = len - 1;
>
> for ( ; ; )
> {
> while (x[0] != x[i])
> i--;
>
> if (is_palin(x + 1, i - 1))
> break;
>
> i--;
> }
>
> return(i + 1);
> }
>
> But I think the time complexity would be quadratic on
> a string such as "aaaaxaaa"
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
