As N=10000 You can go for O(N^2) complexity
and try to do it with level order at every vertex which is a possibility for starting node
This will work if you handle cases correctly
The above algorithm can be extended to handle such cases by adding a special character whenever we encounter NULL in inorder and preorder traversals.
Try to think about think (taken from gfg).
with duplicates - O(N^2)
without duplicates - O(N)
Also don’t use this
inmain.find(insub)!=string::npos
This would give TLE.
1 Like
Did you use KMP? Can you send the code?
code is posted above in post #1
NO KMP. i dont know KMP…just .find function
just added $ functionality @akshitm16
Use KMP search and then try. If you don’t know KMP learn it.
Also-
1 Like
The time complexities of std::string::find and strstr are not specified.
However, in practice it seems that std::string::find is generally implemented “naively” i.e. \mathcal{O}(N \times M):
but according to one guy, gcc’s strstr uses an asymptotically better algorithm:
and so might actually work in situations where std::string::find gets TLE.
3 Likes
c++ reference says it’s naive searching
1 Like
@everule1 @ssjgz @akshitm16 Can anyone confirm what are advanced string matching?
KMP OR Z OR RABIN-KARP?
What should i learn? Is it okay If I learn anyone? which is the most optimised or if it varies case-to-case pls mention cases!
Just wanted to know difference between all three algos…nothing else
They are all completely different. It’s just that all of them can also be use to do string matching. Btw, I wouldn’t recommend rabin karp, because it has hashes. Imo Z algorithm is very simple to implement and deterministic.
Hey I noticed some strange thing. When I am submitting the (.find) which usually gives TLE…5-6 times it is getting AC in 1 out of 5-6 tries. Why so?
@everule1 @ssjgz @akshitm16 @humane
How much time does the AC solution take, and what is the time limit?
Probably just general variation based on server load, etc 
1 Like