Results 1 to 12 of 12

Thread: String search

  1. #1
    tnrh1 is offline Senior Member
    Join Date
    Aug 2011
    Posts
    251
    Rep Power
    4

    Default String search

    Hello,
    if I want to search a certain String in another String for example:
    String st1 = "cat and dog";
    String st2 = "piasjaisfgaasldkdasdidifsdjgioartksflgkpiasjaisfg aasldkdasdidifsdjgioartksflgkpiasjaisfgaasldkdasdi difsdjgioartksflgkpiasjaisfgaasldkdasdidifsdjgioar tksflgk
    piasjaisfgaasldkdasdidifsdjgioartksflgkpiasjaisfga asldkdasdidifsdjgioartksflgkcat and dogpiasjaisfgaasldkdasdidifsdjgioartksflgkpiasjais fgaasldkdasdidifsdjgioartksflgk";

    Searching char by char won't be effective.
    Is there a more efficient way?

  2. #2
    2by4 is offline Banned
    Join Date
    Dec 2011
    Posts
    143
    Rep Power
    0

    Default Re: String search

    Probably not. You would normally look up the String functions in the Java API, decide which one meets your requirements and use that. Behind the scenes it may well be doing a character by character search, although it is possible that it may be optimized at runtime to invoke native byte level searching (still byte by byte).

    Important point is to use the existing String methods.

  3. #3
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default Re: String search

    Have a look at the String API docs for suitable methods.

    [Edit] Slow :( If by "searching char by char" you mean that every character in the long string need be searched then you can do better than that. But we are better off leaving that cleverness to whoever wrote the String class.
    Last edited by pbrockway2; 12-16-2011 at 08:52 PM.

  4. #4
    2by4 is offline Banned
    Join Date
    Dec 2011
    Posts
    143
    Rep Power
    0

    Default Re: String search

    Quote Originally Posted by pbrockway2 View Post
    Have a look at the String API docs for suitable methods.

    [Edit] Slow :( If by "searching char by char" you mean that every character in the long string need be searched then you can do better than that. But we are better off leaving that cleverness to whoever wrote the String class.
    This has got me thinking...
    I would do something like find the sum of the character codes of the substring.
    I would then match that with the equivalent number of characters at the beginning of the main string.
    I would roll through the main string subtracting off the value of the previous start character and adding the new character to the sum and doing a match with the substring. Only if the sums matched would I dig further...(cleverness can be applied to how you dig further as well...)

  5. #5
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default Re: String search

    Wouldn't you still have to access each char to calculate the sum?

    I was thinking of Boyer-Moore, but maybe there are others.

  6. #6
    2by4 is offline Banned
    Join Date
    Dec 2011
    Posts
    143
    Rep Power
    0

    Default Re: String search

    Quote Originally Posted by pbrockway2 View Post
    Wouldn't you still have to access each char to calculate the sum?

    I was thinking of Boyer-Moore, but maybe there are others.
    Yes but not pairs (cartesian product of substring and main string). order of S x M operations.

    My method would be more like 5M operations. So I guess it would be more efficient for S > 5.

    I was really just going off my own immediate creativity. I am sure researched algorithms have squeezed the last drop of efficiency out. :-)

  7. #7
    tnrh1 is offline Senior Member
    Join Date
    Aug 2011
    Posts
    251
    Rep Power
    4

    Default Re: String search

    wow it's so complicated !!!!!!!!!!!!
    Let me re-explain my self with some more details.
    I got 2 strings, one includes a website page(html code of course) and another one holds and html tag.
    And I got another string that holds the stop string ..
    For example:
    st1 = "<html><body><a href="link">The winner is John!</a></body></html>";
    st2 = "<a href="link">";
    st3="</a>"
    Now the code should look for st2 in st1, if it founds it it will print/return the string between st2 and st3 in st1 which is "The winnfer is John"
    I used an example to express my self better because my english is very bad.

    I tried something like:
    Run on the frist string(the big one) till the end.
    if you find a char that equals to the first char in the second string then call a method that checkes if st1 & st2 are equals till the stop string and if it's there it print it and exist from the loop.
    else continue searching ..
    Forgot to mention that it cuts the st1 between st2 and st3.

    "a method that checkes if st1 & st2 are equals till the stop string."
    I send the index of st1 to the method and then it compare the chars in the 2 strings with the same index till it arrives to the stop string (of course only if they are equals).
    it returns null or the string if found.
    And all that code just check if it exist and print it which

    If you can't understand my bad explaination just check the example above and you will know what I mean.
    I hope you guys can help me.

    btw, if the code that I wrote above was working, that thread was closed already :)

    Thanks!

  8. #8
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default Re: String search

    Did you look at the String methods? indexOf() and substring() should be useful.

  9. #9
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,529
    Blog Entries
    7
    Rep Power
    20

    Default Re: String search

    The Knuth Morriis Pratt algorithm, as well as the mentioned Boyer Moore algotihm can find a pattern P in a string S in O(|S|+|P|) steps. The indexOf( ... ) method in Java is a naive algorithm and can take O(|S|*|P|) steps worst case, e.g. S= "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", P= "aaaaab"; computing those sums or hash codes over pattern P doesn't buy you much, e.g. for the two totally different strings "abcde" and "edcba" their sums would be equal.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  10. #10
    tnrh1 is offline Senior Member
    Join Date
    Aug 2011
    Posts
    251
    Rep Power
    4

    Default Re: String search

    Why I made it so complicated?
    The indexOf(String st) is perfect for this case.
    I thought the indexOf is only for chars ..
    stupid me, anyway thank you so much guys for your helpfull information.

  11. #11
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default Re: String search

    You're welcome.

  12. #12
    2by4 is offline Banned
    Join Date
    Dec 2011
    Posts
    143
    Rep Power
    0

    Default Re: String search

    Quote Originally Posted by pbrockway2 View Post
    Wouldn't you still have to access each char to calculate the sum?

    I was thinking of Boyer-Moore, but maybe there are others.
    Thinking about this further, you are correct.

    Testing a function of the set of values gives me no more information than a test of a single value. I would still need n functions to establish equality of n members of the set. The only advantage would be if I could skew the functions in a such a way that the earlier test is more likely to go wrong.

    But worst case scenario is still S X M, not 5S as I claimed earlier.

Similar Threads

  1. How to Search a String from a cell.
    By deshmukh.niraj04 in forum New To Java
    Replies: 5
    Last Post: 03-31-2011, 01:52 PM
  2. Search Substring in String Help Please
    By Kestrel01 in forum New To Java
    Replies: 3
    Last Post: 10-26-2010, 06:48 PM
  3. Using arguments to search for a string
    By MZA in forum New To Java
    Replies: 2
    Last Post: 02-03-2010, 09:22 AM
  4. search with part of string
    By virendra in forum Lucene
    Replies: 1
    Last Post: 01-21-2010, 12:56 PM
  5. Replies: 0
    Last Post: 11-20-2007, 04:59 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •