String search

**tnrh1** · 12-16-2011, 08:22 PM

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?

**2by4** · 12-16-2011, 08:46 PM

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.

**pbrockway2** · 12-16-2011, 08:46 PM

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.

**2by4** · 12-16-2011, 09:24 PM

Originally Posted by pbrockway2

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...)

**pbrockway2** · 12-16-2011, 09:33 PM

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

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

**2by4** · 12-16-2011, 09:41 PM

Originally Posted by pbrockway2

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. :-)

**tnrh1** · 12-17-2011, 05:00 AM

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!

**pbrockway2** · 12-17-2011, 07:40 AM

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

**JosAH** · 12-17-2011, 09:14 AM

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

**tnrh1** · 12-17-2011, 06:43 PM

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.

**pbrockway2** · 12-17-2011, 11:12 PM

You're welcome.

**2by4** · 12-18-2011, 11:27 AM

Originally Posted by pbrockway2

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.