Manacher's Algorithm | Longest Palindromic Substring
ฝัง
- เผยแพร่เมื่อ 30 ก.ย. 2024
- 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.c...
Hard - codeforces.com...
![ได้เวลา! พาน้องแฝดฉีดวัคซีนครบ 1 เดือน🫣 [cc] แดนแพทตี้ SS2 | EP.52 |](http://i.ytimg.com/vi/IzeLtaXBLNE/mqdefault.jpg)
can not understand the psudo code in over 2 times watching this, I am ok with O(n)2.
this was the best manachers algo explanation i found, better that tushar roy, tech dose, nick white
and so many others
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
rather than adding hashes, you can just compare i,i (i being the centre). and make a function for it and fn(i,i) for odd, fn(i,i+1) for even.
Thank you a lot. Only this video deeply explained an algorithm!
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
//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
best explanation found till now for this algorithm.🔥🔥
very clear and comprehensive video. The best explanation for Manacher's Algorithm!
Well Explained! Among all the videos about Manacher's Algorithm, your explanation is best. Thank you for making this video.
Only one doubt why you have written, If(s[i-k]!=s[i+k]) --k
Great Video. Thanks for the simple and intuitive explanation!
I think the algorithm will fail for a test case such as "cbbd"....
So let’s see what happens here
We rewrite your test case into
# c # b # b # d #
And then we simulate the algorithm…
I will do it manually…
i = 0
l = 0, r = -1
i is bigger than r, k = 0
We expand k to 1 and cannot further due to the left bound limitation, k = 0 again, p[0] = 0
We extend l to 0 and r to 0
i = 1
i is bigger than r again so k = 0
We push k to 2 and it fails due to mismatch
k is 1 then
p[1] = 1
We extend l to 0 and r to 2
i = 2
i is equal to r so we pass to else
j is equal to 0, thus k starts at 0
We run the while loop and it fails at k = 1 due to mismatch then k = 0
p[2] = 0, l = 2 and r = 2
i = 3
i is bigger than r, so k = 0
After while it fails at k = 2 so k is 1, so p[3] = 1 and l = 2, r = 4
i = 4
i isn’t bigger than r
j = 2, so p[j] = 0, thus k becomes 0, it fails for k = 3 so k = 2, p[4] = 2, l = 2, r = 6
i = 5
i isn’t bigger than r
j = 3, p[j] = 1, k = min(1, 6-5)
we start at k = 1, it fails at 2 so k stays at 1
p[5] = 1
l = 4, r = 6
i = 6
i isn’t bigger than r
j = 4, p[j] = 2, so k is min(2, 0)
k fails for 1 due to mismatch and k = 0, so p[6] = 0, l = 6, r = 6
i = 7
i is bigger than r so k = 0
it fails at k = 1 cause further it cannot extend, p[7] = 1, l = 6, r = 8
i = 8
i isn’t bigger than r so j = 6, k = min(0, 0) and then fails due to the range, so p[8] = 0, l = 8, r = 8, the end of algorithm, let’s see what’s the outcome…
# c # b # b # d #
0 1 0 1 2 1 0 1 0
Seems correct to me
@aishwaryastogi7265
There is a little bug in the code, the --k step after expansion is mandatory.
Can you also consider making a video on Ford Fulkerson max flow algorithm??
Sure!
All of your videos are just amazing !
Please make more videos...!
Thanks a lot !
Nice explanation!
Best explaination on the internet
Great explanation brother.....
Just watching first 4 mins and I found its very fluent and easy to understand. 🙏
greatest explanation of this algorithm on the internet.
Great explanation, thank you!
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/
good explaination
one of the youtuber that can explain manacher pretty well , respect
Brother why did u leave making videos.
They are all exceptional..
I will even subscribe ur channel.now
Plz keep on uoloading
Nice video
Really good video 🙂🙂🙂
Thank you. It is very well explained.
bhai pseodo code link wagera de diya karo
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
great!
Bro your videos are literally awesome.
Really great explainaion
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 :)
Thank you, your video helps a lot.
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.
best explanatiion!!
Good explanation
❤❤❤
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.
brilliant explanation sir ! , thanks a lot