Find a string in another string

[Richard Bos]

For example, if I look for the string "searchString" in the string "jlh ahs
dalskd" then it is of course NOT found, but if I instead look for the same
string in "lkasjalskj searchString sedlfksd" then it IS found.

Erm... what about strstr()?

Richard

 

[MM]

Hello there

I need a way to efficiently check if a string I specify can be found in
another string.

For example, if I look for the string "searchString" in the string "jlh ahs
dalskd" then it is of course NOT found, but if I instead look for the same
string in "lkasjalskj searchString sedlfksd" then it IS found.

So, is there any (fairly) efficient way to do this?

Many thanks in advance,

MM

 

[Lew Pitcher]

Hello there

I need a way to efficiently check if a string I specify can be found in
another string.

strstr(), although I can't vouch for it's efficiency on your platform


--
Lew Pitcher
IT Consultant, Enterprise Technology Solutions
Toronto Dominion Bank Financial Group

(Opinions expressed are my own, not my employers')

 

[Eric Sosman]

Hello there

I need a way to efficiently check if a string I specify can be found in
another string.

For example, if I look for the string "searchString" in the string "jlh ahs
dalskd" then it is of course NOT found, but if I instead look for the same
string in "lkasjalskj searchString sedlfksd" then it IS found.

So, is there any (fairly) efficient way to do this?

The C language Standard makes no guarantees -- indeed,
it says nothing at all -- about the efficiency of any
construct or library function. Still, a few guidelines:

- If you're doing just a few such searches, use
the strstr() function

- If you're doing many searches using the same
"SearchString" in different target strings,
implement something like the Bayer-Moore
algorithm

- If you're doing many searches using different
"SearchString"s in the same target string,
implement something like Patricia (see Knuth
TAOCP Volume III)

- If you're doing many searches using different
"SearchStrings" *and* different target strings,
use the strstr() function

.... but in no case should you go to the effort of Bayer-Moore
or Patricia until you've *measured* your program's performance
and *proven* to yourself that searching for strings within
strings takes unacceptably long. Start with strstr() and
adopt fancier solutions only if they're proven necessary --
and even then, it might turn out that the "best" approach
is to re-think the program design to obviate the searches.

 

[MM]

Erm... what about strstr()?

Richard

Ah, looks nice and simple. Thanks!

And if I want to use for example strstr() to search for a substring in only
the first n characters of the "main" string? I want to do something like
this (although this does not work, of course, since mainString[1..n] is not
the correct way to "cut" a string):

pos = strstr(mainString[1..n],searchString);

//MM

 

[Dan Pop]

Erm... what about strstr()?

And if I want to use for example strstr() to search for a substring in only
the first n characters of the "main" string? I want to do something like
this (although this does not work, of course, since mainString[1..n] is not
the correct way to "cut" a string):

pos = strstr(mainString[1..n],searchString);

If mainString is writable, temporarily replace mainString[n] by a null
character. Restore it after the strstr call. Otherwise, make a copy of
the first n characters of mainString and use it instead. C has no syntax
for specifying substrings.

It's much simpler to specify the "tail" of a C string: mainString + n
means the string containing everything but the first n characters of
mainString.

Dan

 

[Chris Torek]

... but in no case should you go to the effort of Bayer-Moore
or Patricia until you've *measured* your program's performance
and *proven* to yourself that searching for strings within
strings takes unacceptably long. ...

Right. But note that one will have better luck searching for the
correct name, "Boyer-Moore". (The respelled name *does* appear
to be in at least somewhat common use, but Bob Boyer's name really
is spelled "Boyer", not "Bayer". See
<http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/>
for instance.)

 

[Juergen Heinzl]

Hello there

I need a way to efficiently check if a string I specify can be found in
another string.

For example, if I look for the string "searchString" in the string "jlh ahs
dalskd" then it is of course NOT found, but if I instead look for the same
string in "lkasjalskj searchString sedlfksd" then it IS found.

So, is there any (fairly) efficient way to do this?

[-]
More than one

You C library'd provide strstr(), which is often based on or
implented as the Boyer-Moore algorithm. If your strings to
be searched in are very short or very long other methods might
be more efficient, so if you can time a test application to see
whether (your) strstr() is good enough for your problem.

Ta',
Juergen

 

[Glen Herrmannsfeldt]

(snip)

... but in no case should you go to the effort of Bayer-Moore
or Patricia until you've *measured* your program's performance
and *proven* to yourself that searching for strings within
strings takes unacceptably long. Start with strstr() and
adopt fancier solutions only if they're proven necessary --
and even then, it might turn out that the "best" approach
is to re-think the program design to obviate the searches.

Unless, of course, this is a homework assignment to use such an algorithm.

-- glen