Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Find a string in another string (http://www.velocityreviews.com/forums/t314697-find-a-string-in-another-string.html)

Richard Bos 08-11-2003 11:27 AM

Re: Find a string in another string
 
"MM" <dobedidoo@yahoo.se> wrote:

> 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 08-11-2003 01:39 PM

Find a string in another string
 
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 08-11-2003 02:06 PM

Re: Find a string in another string
 
On Mon, 11 Aug 2003 15:39:41 +0200, "MM" <dobedidoo@yahoo.se> wrote:

>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 08-11-2003 02:42 PM

Re: Find a string in another string
 
MM wrote:
>
> 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.

--
Eric.Sosman@sun.com

MM 08-11-2003 02:49 PM

Re: Find a string in another string
 

"Richard Bos" <rlb@hoekstra-uitgeverij.nl> wrote in message
news:3f377d9a.2240582727@news.nl.net...
> "MM" <dobedidoo@yahoo.se> wrote:
>
> > 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


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 08-11-2003 03:14 PM

Re: Find a string in another string
 
In <K1OZa.3628$Y5.1008@nntpserver.swip.net> "MM" <dobedidoo@yahoo.se> writes:


>"Richard Bos" <rlb@hoekstra-uitgeverij.nl> wrote in message
>news:3f377d9a.2240582727@news.nl.net...
>> "MM" <dobedidoo@yahoo.se> wrote:
>>
>> > 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()?
>>

>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
--
Dan Pop
DESY Zeuthen, RZ group
Email: Dan.Pop@ifh.de

Chris Torek 08-12-2003 02:32 AM

Re: Find a string in another string
 
In article <3F37AB60.196F394E@sun.com>
Eric Sosman <Eric.Sosman@Sun.COM> writes:
>... 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.)
--
In-Real-Life: Chris Torek, Wind River Systems (BSD engineering)
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: forget about it http://67.40.109.61/torek/index.html (for the moment)
Reading email is like searching for food in the garbage, thanks to spammers.

Juergen Heinzl 08-14-2003 01:46 PM

Re: Find a string in another string
 
In article <s0NZa.3623$Y5.1025@nntpserver.swip.net>, MM wrote:
> 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 8-)

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

--
\ Real name : Juergen Heinzl \ no flames /
\ EMail Private : juergen@manannan.org \ send money instead /

Glen Herrmannsfeldt 08-16-2003 01:52 AM

Re: Find a string in another string
 

"Eric Sosman" <Eric.Sosman@sun.com> wrote in message
news:3F37AB60.196F394E@sun.com...

(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




All times are GMT. The time now is 06:13 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.