Find a string in another string

Discussion in 'C Programming' started by Richard Bos, Aug 11, 2003.

  1. Richard Bos

    Richard Bos Guest

    "MM" <> 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
     
    Richard Bos, Aug 11, 2003
    #1
    1. Advertising

  2. Richard Bos

    MM Guest

    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
     
    MM, Aug 11, 2003
    #2
    1. Advertising

  3. Richard Bos

    Lew Pitcher Guest

    On Mon, 11 Aug 2003 15:39:41 +0200, "MM" <> 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')
     
    Lew Pitcher, Aug 11, 2003
    #3
  4. Richard Bos

    Eric Sosman Guest

    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, Aug 11, 2003
    #4
  5. Richard Bos

    MM Guest

    "Richard Bos" <> wrote in message
    news:...
    > "MM" <> 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
     
    MM, Aug 11, 2003
    #5
  6. Richard Bos

    Dan Pop Guest

    In <K1OZa.3628$> "MM" <> writes:


    >"Richard Bos" <> wrote in message
    >news:...
    >> "MM" <> 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, Aug 11, 2003
    #6
  7. Richard Bos

    Chris Torek Guest

    In article <>
    Eric Sosman <> 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 (40°39.22'N, 111°50.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.
     
    Chris Torek, Aug 12, 2003
    #7
  8. In article <s0NZa.3623$>, 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 :cool:

    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 : \ send money instead /
     
    Juergen Heinzl, Aug 14, 2003
    #8
  9. "Eric Sosman" <> wrote in message
    news:...

    (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
     
    Glen Herrmannsfeldt, Aug 16, 2003
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    17
    Views:
    847
    Hiran Chaudhuri
    Dec 6, 2005
  2. Wybo Dekker
    Replies:
    1
    Views:
    381
    Yukihiro Matsumoto
    Nov 15, 2005
  3. nani
    Replies:
    2
    Views:
    171
    comp.llang.perl.moderated
    Mar 14, 2008
  4. vdvorkin
    Replies:
    0
    Views:
    425
    vdvorkin
    Feb 10, 2011
  5. vdvorkin
    Replies:
    3
    Views:
    832
    vdvorkin
    Feb 14, 2011
Loading...

Share This Page