Re: speed up u8_strstr

[Pádraig Brady]

On 31/07/10 20:48, Bruno Haible wrote:
> Hi Pádraig,
> 
>>> the u8_strstr function.
>>
>> I wonder could we speed that up for UTF-8
>> by just deferring to strstr() ?
> 
> This is a good idea, because the naïve implementation of u8_strstr is
> quadratic (O(n²)), whereas for strstr we now have an O(n) algorithm.
> 
> But at the same time, can you also try to apply the O(n) algorithm to
> u16_strstr and u32_strstr?
> 
> Bruno
> 
Attached is a first attempt at this.
Questions I have are:

Is it OK to include str-mp.h and malloca
in unistr/ modules like I do?

I'm thinking of adding an alarm(5) to the test
to enforce the performance check.

cheers,
Pádraig.

fast-u-strstr.diff
Description: Text Data