Click here to Skip to main content
13,259,194 members (53,378 online)
Rate this:
Please Sign up or sign in to vote.
See more:
Hey folks,

I have written a function which searches for a given pattern in a given string and
returns yes if the pattern is in the function and no respectively. Plus it also returns the position from where the pattern occurred. e.g., string "hello world" contains pattern "wor" starting from position: 6.

I would be very glad if you could look at my code and provide me with feedback whether it could be more improved or optimized???? Thank you. (ps. the code is working of course, just I am interested in optimization if it is possible).
Posted 23-Sep-12 7:38am
Updated 30-Oct-12 9:53am
Sergey Alexandrovich Kryukov 23-Sep-12 12:54pm
First of all, did you test it? Are you sure it works in all imaginable cases?
dmcr_ 23-Sep-12 12:57pm
Yes yes it works as far as I have tested.
Minor comment: the functions length() I mentioned above are specified elsewhere and they also work :).
Sergey Alexandrovich Kryukov 23-Sep-12 14:34pm
Good. I mean I saw the well-known algorithm (I would need some time to find it again); and it looks like the problem is not as trivial as it might seem. If you can proof that your algorithm is correct, it is implemented in a very compact way, which is good, but performance could be a problem, due to two nested loops.
dmcr_ 23-Sep-12 16:55pm
Dear Sergey thank you for your reply - please see my comment I did to user: "pasztorpisti".
pasztorpisti 23-Sep-12 15:46pm
Well, either use an existing search implementation, or make the writing of substring serach a bit more challenging for example by making it more efficient for example with KMP:
There are other bruteforce low-level technical tricks to make your search method faster (like comparing machine-word wide data whenever possible) but playing with algorithms and KMP will be much more fun for you.
dmcr_ 23-Sep-12 16:54pm
Hey thanks for the links. Actually on one of those web sites they refer to my solution as naive: because of two loops I think (my implementation has complexity O(x1*y1) due to this). Anyway it was interesting to hear it is a mathematical problem and there exist algorithms to solve it.
pasztorpisti 23-Sep-12 17:00pm
You are welcome! Programming is usually about much more than changing bits in the memory - its also about planning, designing (this involves algorithms/data structures) - thinking in general. :-)
pasztorpisti 23-Sep-12 17:10pm
One more thing: Knowing this algorithm is good even if you have ready-made string search functions becuase: strings are just arrays/sequences of characters. Some day you might have to work with arrays/sequences of other kind of data (not characters) and then knowing KMP or a similar algorithm can come handy.
Sergey Alexandrovich Kryukov 23-Sep-12 19:46pm
This is related to one more benefit of reinventing the wheels. Many thing that reinventing the wheel contradicts to reuse. This is not true at all. When the wheel is reinvented, it can be reused.

So, what is that benefit?

This is the reading on the know solutions and other works. Before one breaks some teeth on the problem, such reading might be not so effective; it's hard to evaluate the problem correctly, really appreciate the available work and even put the available solutions to work in the most efficient ways (for more complex problems, of course).

However, after the attempt to reinvent the wheel, even not very successful, one can understand existing solutions much better. I don't even mention rare but very important cases of successfully reinvented wheels. They are rare, but are critically important to our progress. They are based on critical thinking and the ability to not be magically affected by the authority, which is critically important.

Overall, I always considered the principle "don't reinvent the wheel" as counterproductive; and I cannot be fooled by references to "reuse" -- the reuse is something different, not contradicting the idea to reinvent the wheel. It's a good thing.

Actually, I'm going to up-vote the OP's question even despite the not so effective solution. And I see that OP already understand what is that computational complexity.

pasztorpisti 23-Sep-12 20:01pm
I always felt bad (maybe angry?) when some people told me "not to reinvent the wheel, reuse instead" during my hobby projects but never formulated and generalized the reason/answer to that like you did. In general its good to know how things work inside, and successful/unsuccessful attempts drive evolution. I remember when I started to write a small regex library and when it was ready with its minimalist feature set I just realized how much more other libraries knew and how much work would it be to incorporate them into my own stuff. And this is just one of my 'failures', still as you said the time spent on such successful/unsuccessful attempts isn't wasted time. You understand the related problems floating around a ready-made solution much better.
Sergey Alexandrovich Kryukov 23-Sep-12 20:45pm
Of course. The only problem is that you cannot try to reinvent everything, but this is what the experience/intuition and creative approach are for.
pasztorpisti 23-Sep-12 20:50pm
Sometimes you don't know what the wheel is like the OP. :-) Sometimes I start rewriting stuff because I want only a subset of its functionality with less/cleaner code - that was my intention for example with the regex library. Then I realized that sometimes I need unicode support, ignore-case functionality, non-greedy matching, ...
Sergey Alexandrovich Kryukov 23-Sep-12 21:41pm
Yes, subset. This is one of the cases. There are cases where a general solution already exists, but solving the more special problem from scratch could dramatically improve code, for example performance.

My friend gave me a good example of the fallacy of the engineering myths. One of them goes "the main thing in engineering education is how to read literature". Aha, now... So one such engineers had a problem to write the median filter; and the formulation requires to have a sorted sequence from input, and then add new elements sorting the subset withing the width of the filter each time.

That guy thinks: aha, the sorting... let's read... what is available? Quick sort. OK, quick; do we need slow sorting? No, so let's take quick sort... blah-blah... the code is ready.

And my friend told "fool you are fool; you needed to add element to already sorted sequence, not sort it each time". See the difference.

So, yes, the subset is just one of the things where... basically, a brain is really needed, not a clever book...

pasztorpisti 24-Sep-12 4:39am
Absolutely agree. Anyway, the sorting/quicksort raises some good interview questions... :-)
Sergey Alexandrovich Kryukov 23-Sep-12 19:24pm
Yes, KMP is what I meant. It's really challenging because despite simplicity, KMP is more efficient and actually not so trivial. I would rather up-voted this comment by 5, than your solution, because I'm pretty much sure OP knows how to call the library methods. :-)
pasztorpisti 23-Sep-12 19:29pm
Well, I'm too much used to beggars and homework owners... Relatively rare to see someone who comes to learn and/or for a challenge.
Sergey Alexandrovich Kryukov 23-Sep-12 19:55pm
This person is apparently not like those...
Rate this: bad
Please Sign up or sign in to vote.

Solution 1

You could also check the libraries for standard functions such as strstr()[^].
dmcr_ 23-Sep-12 12:46pm
thank you for the reference. but I was just interested how "good" was my solution
pasztorpisti 23-Sep-12 13:28pm
Reinventing small wheels like this is never good.
Sergey Alexandrovich Kryukov 23-Sep-12 19:21pm
I must disagree, especially about your "never". The history of science and technology is full of examples of re-inventing the small wheels which all thought to be useless but brought very good results. Amazingly, that some of such inventions were about real wheels -- it's enough to look at the modern advanced car or motorcycle wheel to see it.
pasztorpisti 23-Sep-12 19:25pm
You are right. In one of my later comments below the question I came to the conclusion that its good that this padavan is searching a solution to find a sequence in another sequence.
Sergey Alexandrovich Kryukov 23-Sep-12 19:58pm
Great. Thank you for understanding.
dmcr_ 24-Sep-12 8:24am
Dear Sergey and pasztorpisti,
Thank you for your comments and discussions. I would like to clarify one thing, I should have better done this before, but anyway. When pasztorpisti told me: it is not a good idea to reinvent the wheel - I didn't reply. However, my plan was not to reinvent the wheel, I was merely trying to see how I would be able to solve this (maybe not very difficult) task. I hope it makes my intentions clear now. Thank you.
Sergey Alexandrovich Kryukov 24-Sep-12 18:23pm
I could assume that it would be exactly your motivation; and I really respect you for that. That's why I decided to up-vote the question and started this discussion which we completed understanding each other really well.

Good luck; and you further posts are very welcome.
dmcr_ 25-Sep-12 7:33am
Dear Sergey, Thank you very much for your comments! :)
Sergey Alexandrovich Kryukov 25-Sep-12 14:13pm
My pleasure.
Rate this: bad
Please Sign up or sign in to vote.

Solution 2

You can go with the mentioned strstr() or if you are using std::string then use std::string::find()[^].

For searching very complex patterns use regular expressions: The 30 Minute Regex Tutorial[^]

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month

Advertise | Privacy |
Web01 | 2.8.171114.1 | Last Updated 30 Oct 2012
Copyright © CodeProject, 1999-2017
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100