Re: Evaluation of C program

Walter Roberson wrote:
In article <1140113852.635717.152500@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<morphex@xxxxxxxxx> wrote:
I'm a python programmer that's started to play a bit with C as I'll
probably have to make C extensions eventually.. I made this little
program that I'd like to get feedback on, it's basically a find
substring and return pointer to it function and tests for it..

Could this be done better/differently? Is anything fundamentally
wrong?

Suppose you don't find a match the first iteration through
because the 10th character in the trial substring does not match
the 10th character in the input string. You then loop back
and start testing from the substring again from the second
character of the input string -- ignoring all the information
you could have gleened by paying attention to what was in
offsets 1 thru 9 that you have already looked at.

Suppose for example that what you found at the 10th character at the
input string was an 'X', and there are no occurances of 'X' in the
trial substring. A moment's reflection would show you that in
such an instance you would be able to skip testing for the
substring as starting from 1 thru 9, since that 'X' will still be
there at offset 9 blocking any possible match.

What this tells you is that there are algorithms which can be
much faster than your search algorithm. Indeed, there is an entire
literature on search algorithms. Some are probably mentioned in the C
FAQ or by googling for "string search algorithms".

Boyer Horspool Moore comes to mind. I implemented it with
a circular buffer; it's fast.

Stijn

.

Relevant Pages

  • Re: Evaluation of C program
    ... goto success; ... because the 10th character in the trial substring does not match ... the 10th character in the input string. ... much faster than your search algorithm. ...
    (comp.lang.c)
  • Re: Evaluation of C program
    ... substring and return pointer to it function and tests for it.. ... strings can be longer than an 'int' can hold. ... the 10th character in the input string. ... much faster than your search algorithm. ...
    (comp.lang.c)
  • Re: Evaluation of C program
    ... substring and return pointer to it function and tests for it.. ... strings can be longer than an 'int' can hold. ... the 10th character in the input string. ...
    (comp.lang.c)
  • Re: How to return a variable length substring from a function ?
    ... I have a function that returns a variable length character substring. ... Depending on the input, the output is either 1 to 3 characters long. ... strings within fixed length strings. ...
    (comp.lang.fortran)
  • Re: Help with Replace()
    ... but you're asking to return 1 character, from the 16th....this is the "-" letter, which is now null, hence the null string returned. ... The actual Variable StrToSearch was valued with the " " ... String expression containing sub string to replace. ... Substring being searched for. ...
    (microsoft.public.excel.programming)