Manacher's Algorithm | Longest Palindromic Substring
Vložit
- čas přidán 26. 03. 2020
- In this video I will be discussing Manacher's algorithm which is used to find the longest palindromic substring in linear time. Its a fairly complex algorithm and understanding its time complexity is the hardest part. So, in this video I will help you understand it to the fullest.
Practice problems :
Easy - www.codechef.com/problems/PALIN3
Hard - codeforces.com/contest/1080/p...
Too good. Thanks for explaining it in so simple terms and also for covering every case.
this is the best video among all the videos on youtube explaining manacher's algorithm
best explanation found till now for this algorithm.🔥🔥
Well Explained! Among all the videos about Manacher's Algorithm, your explanation is best. Thank you for making this video.
this was the best manachers algo explanation i found, better that tushar roy, tech dose, nick white
and so many others
very clear and comprehensive video. The best explanation for Manacher's Algorithm!
Great Video. Thanks for the simple and intuitive explanation!
All of your videos are just amazing !
Please make more videos...!
Thanks a lot !
Just watching first 4 mins and I found its very fluent and easy to understand. 🙏
one of the youtuber that can explain manacher pretty well , respect
Thank you, your video helps a lot.
Bro your videos are literally awesome.
Thank you. It is very well explained.
Best explaination on the internet
Nice explanation!
Great explanation brother.....
Really great explainaion
good explaination
best explanatiion!!
Can you also consider making a video on Ford Fulkerson max flow algorithm??
Sure!
Good explanation
Nice video
Please provide a problem link related to this algorithm . you can provide it in description for further videos.
Ive added practice problems in the description.
There is a little bug in the code, the --k step after expansion is mandatory.
Really good video 🙂🙂🙂
Can you make a video on sweep line algo as a whole?
I'll consider it. For now you can refer www.topcoder.com/community/competitive-programming/tutorials/line-sweep-algorithms/
great!
Only one doubt why you have written, If(s[i-k]!=s[i+k]) --k
Best !!!!!!
I want to ask one thing that does this code only work for showing odd length substrings or will it work for showing even length palindromic substrings also.
I tried for the string "bbbb" on this code and this code is not working.
After seeing many videos, I finally understood Manacher's algorithm seeing this video. Thanks a lot and hoping to see more videos from this channel like this.
Edit:
One more thing I would like ask is this condition
if(S[i-k]!=s[i+k]) required as I am facing problem with that line of code and finally removed and your code is running perfect for finding odd palindromes only.
Once again Thanks for amazing explanation of concept.
thats great man
you need to add # yourself
Case 2 shown during 13:13 is wrong. p[i] >= p[i'] could be false, the palindrome centered in s_i' could extend back far beyond s_l. The conclusion that p[i] must be greater or equal to r-i is right, however.
Yes, Case 2 is wrong, zxaxz#zxaxp , where i = index of 2nd a
brilliant explanation sir ! , thanks a lot
Can u make a solution video for the PALIN3 problem .. I am unable to understand the precomputation required in it... thanks
You can checkout my explanation here : discuss.codechef.com/t/palin3-editorial/4906/6?u=vedhant
@@fluentalgorithms4847 " To find ans[i], ans[i] = cnt[i+k][s[i]%3] - cnt[i][s[i]%3] will not work because sum[i] would have contributed to the sum right of I "
Can u pls explain this line once? thanks
I have updated my explanation here : discuss.codechef.com/t/palin3-editorial/4906/6?u=vedhant
@@fluentalgorithms4847 Thanks a lot ... finally understood :)
Brother why did u leave making videos.
They are all exceptional..
I will even subscribe ur channel.now
Plz keep on uoloading
bhai pseodo code link wagera de diya karo
❤❤❤
can not understand the psudo code in over 2 times watching this, I am ok with O(n)2.
I think the algorithm will fail for a test case such as "cbbd"....
//c++ code
class Solution {
public:
string getModifiedString(string s, int n){
string sb="";
for(int i = 0; i < n; i++){
sb.append("#");
sb+=s[i];
}
sb.append("#");
return sb;
}
public:
string longestPalindrome(string s1) {
int m=s1.size();
string s=getModifiedString(s1,m);// expand the string for even expansion of string
cout
Great video, but try to make video at max 10 minutes it will help to retain viewers, because everyone is searching for solution in short time.