string::find complexity.

[Paolo Carlini]

Ian Lance Taylor wrote:

>Of course, KMP is only a win when the length of the string is
>significantly greater than the length of the pattern.
>  
>
... and, what happens when that't not true? Does it lose bad?

>A partial KMP that is often effective in practice is to first search
>backward through the pattern for the last but one occurrence of the
>last character.  Then check whether the last character matches.  If it
>does, do a full comparison.  If it doesn't, increment by the distance
>between the last character and the immediately previous
>occurrence--the length of the pattern if you are lucky.
>  
>
Thanks. By the way, there are good expositions of the algorithm around:

    http://www.ics.uci.edu/~eppstein/161/960227.html

Paolo.