Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++
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 6:38am
Edited 30-Oct-12 8:53am
v2
Comments
Sergey Alexandrovich Kryukov at 23-Sep-12 12:54pm
   
First of all, did you test it? Are you sure it works in all imaginable cases?
--SA
Sergey Alexandrovich Kryukov at 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.
--SA
pasztorpisti at 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:
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
http://www.ics.uci.edu/~eppstein/161/960227.html
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.
pasztorpisti at 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 at 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 at 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.
 
--SA
pasztorpisti at 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 at 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.
--SA
pasztorpisti at 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 at 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...
 
--SA
pasztorpisti at 24-Sep-12 4:39am
   
Absolutely agree. Anyway, the sorting/quicksort raises some good interview questions... :-)
Sergey Alexandrovich Kryukov at 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. :-)
--SA
pasztorpisti at 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 at 23-Sep-12 19:55pm
   
This person is apparently not like those...
--SA
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

You could also check the libraries for standard functions such as strstr()[^].
  Permalink  
Comments
pasztorpisti at 23-Sep-12 13:28pm
   
Reinventing small wheels like this is never good.
Sergey Alexandrovich Kryukov at 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.
--SA
pasztorpisti at 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 at 23-Sep-12 19:58pm
   
Great. Thank you for understanding.
--SA
Sergey Alexandrovich Kryukov at 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.
--SA
Sergey Alexandrovich Kryukov at 25-Sep-12 14:13pm
   
My pleasure.
--SA
Rate this: bad
good
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[^]
  Permalink  
v2

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

  Print Answers RSS
0 Sergey Alexandrovich Kryukov 404
1 Richard MacCutchan 240
2 OriginalGriff 230
3 Jared Sanow 145
4 Vinay Mistry 143
0 Sergey Alexandrovich Kryukov 5,955
1 OriginalGriff 4,805
2 CPallini 2,473
3 Abhinav S 1,507
4 Richard MacCutchan 1,437


Advertise | Privacy | Mobile
Web01 | 2.8.140814.1 | Last Updated 30 Oct 2012
Copyright © CodeProject, 1999-2014
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