Search a pattern in given string

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

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.

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

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.

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

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

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

Absolutely agree. Anyway, the sorting/quicksort raises some good interview questions... :-)

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

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.

This person is apparently not like those...
--SA