Manacher Algorithm for Strings | Understanding, Proof and Implementation | Palindromes | VIvek Gupta
Vložit
- čas přidán 9. 12. 2022
- Manacher's Algorithm is used to solve many problems related to Palindromes and is also asked in coding tests and interviews.
🔴 Here are some good practice problems:
judge.yosupo.jp/problem/enume...
cses.fi/problemset/task/1111
www.spoj.com/problems/NUMOFPAL/
codeforces.com/contest/1326/p...
✨ Hashtags ✨
#VivekGupta #Competititve #CPStreams #codechef #codeforces #engineering #internship
-------------------------------------------------------------------------------------------------------------
If you are a beginner, here are some resources to start with :
✅ Free Language course with certificate that i taught - bit.ly/3I52EAb
✅ More free courses - bit.ly/3SKoCNO
If you are looking to train in a commado like regime for acing DSA (with DEV and System Design covered for placement too), do checkout :
🔴 bit.ly/3SKoM7S
If you want to connect over social media or want more resources : linktr.ee/vivek_gupta
Video suggestion: Generating Functions
Believe me I have watched lot of videos of explanations of manacher, but this is one is the best explanation and intuitions. Loved it and subscribed.
Thank you very much for this impeccable explanation. After watching your video, I don't have even a single doubt about the algorithm. You should definitely continue with this type of content!
Such a great explanation , well explained intuition behind algorithm.
Great Explanation! Thanks.
Thanks Bhaiya for amazing explanation
I saw your sos dp and you nailed it
Thanks brother for such nice explanation😊
thanks a lot waiting for more such content
Great Video Vivek!! Thanks!!
Thanks for explaining so nicely
Thanks bro for wonderful explanation
Leetcode's 5. Longest Palindromic Substring Solution using his manacher template.
class Manacher{
string t;
vector p;
int lpsStart, lpsLength;
public:
Manacher(string s){
for(char i: s){
t += string("#") + i;
}
t += string("#");
build();
}
// p[i] = defines how many length of palindrome we have at index i.
// Actual length of palindrome at p[i] is p[i] - 1, as We initially assigned 1 value to every p[i], So '#' characters also got length 1, which is why we have to subtract 1.
void build(){
int n = t.size();
p.resize(n, 1);
int l = 1, r = 1;
for(int i = 1; i < n; i++){
if(l + r - i >= 0) p[i] = max(1, min(r - i, p[l + r - i]));
while(i - p[i] >= 0 && i + p[i] < n && t[i - p[i]] == t[i + p[i]]) p[i]++;
if(i + p[i] > r){
l = i - p[i];
r = i + p[i];
if(lpsLength < p[i]){
lpsStart = l + 2;
lpsLength = p[i] - 1;
}
}
}
}
int getLongest(int center, bool odd){
int position = 2 * center + 1 + (!odd);
return p[position] - 1;
}
// (r - l + 1) is the size of the current window, if current window size comes under its center's biggest palindrome, then it means it's also palindrome, as part of palindrome is also palindrome.
bool checkPalindrome(int l, int r){
if((r - l + 1)
Thanks for the contribution!
It is not working
@@arnavsinghal9662 just initialize the values of lpsStart and lpsLength to 1, then its working. Actually it was working earlier, now its taking any garbage values, thats why its not giving right output.
class Manacher{
string t;
vector p;
int lpsStart = 1, lpsLength = 1;
public:
Manacher(string s){
for(char i: s){
t += string("#") + i;
}
t += string("#");
build();
}
// p[i] = defines how many length of palindrome we have at index i.
// Actual length of palindrome at p[i] is p[i] - 1, as We initially assigned 1 value to every p[i], So '#' characters also got length 1, which is why we have to subtract 1.
void build(){
int n = t.size();
p.resize(n, 1);
int l = 1, r = 1;
for(int i = 1; i < n; i++){
if(l + r - i >= 0) p[i] = max(1, min(r - i, p[l + r - i]));
while(i - p[i] >= 0 && i + p[i] < n && t[i - p[i]] == t[i + p[i]]) p[i]++;
if(i + p[i] > r){
l = i - p[i];
r = i + p[i];
if(lpsLength < p[i]){
lpsStart = l + 2;
lpsLength = p[i] - 1;
}
}
}
}
int getLongest(int center, bool odd){
int position = 2 * center + 1 + (!odd);
return p[position] - 1;
}
// (r - l + 1) is the size of the current window, if current window size comes under its center's biggest palindrome, then it means it's also palindrome, as part of palindrome is also palindrome.
bool checkPalindrome(int l, int r){
if((r - l + 1)
After spending sometime with this code it blew away my head.... i found further on cp-algo.. doesn't work with printing even length
Best resource for Manacher
Nicely explained
In the reply to my previous comment you said that if we know the max palindrome length at each centre ceil( max/2 )would give us length and it indeed worked. But I am not understanding why are we doing ceil(max/2) for the count of palindrome at each centre?and max length of palindrome at a centre is obviously p[i] right?
Finally, I understood Manacher thanks to you.
PS: Just in case, if you're in a bad mood today, I hope this comment will cheer you up.
welcome back
WHERE DO I GET DP WORKSHOP PRACTICE PROBLEMS , CANNOT FIND ON ALGOZENITH WEBISITE , HELP PLS ,
P.S : amazin series, will buy algozenith surely in future
Thanks a ton Man 🤟
while updating l and r we just checked whether i+p[i] crossed r or not but we never checked whether this is longer than the longest found till now or not. We have to check it ryt since l,r are boundaries of longest found palindromes
its not the longest one… but the farthest ending dor the bounding box
Tysm bro ❤❤
Hey I had a question,after generation of the p array,how can we find the total number of palindromic substrings?I tried doing the sum of all elements of P array but the answer comes out to be inconsistent for different lengths of the string.
Every palidrome has a center. Find num of palindrome at each center. if you know the max len at each center… ciel (max /2) should give you count.
Thanks. Please makes a tutorial on policy based Data structure
explanation was superb!!
Do you have any plans for resuming your codeforces weekly streams ?
I can pick good idea problems once in a while.. But weekly might not be possible due to more work these days :,(
@@vivekgupta3484how about two post contest discussions in a video a month ?
@@ajitkumarsingh871I feel many creators are already doing this. I want to deliver something that is not being created.
What is this black screen application you're using for teaching purposes?
I am using openboard.
i m facing difficulty in solving array, when i solve array question . the output of solution is always says that my array is overflow!! what should i do??
Create array of sufficiently large size!
How can we find count of sub palindrome using rolling hash?
you will have to build the manacher array by using binary search at every center.
bhai ye video kal mil jata
i think there is a array out of bound problem with the string
"yvaamavy"
Bro Game Theory mai ek playlist banalo plss
actually this is a really good idea
The algorithm does not look like O(N).
But it is :P
As per my analysis it has a linear time frame and not o(n). I did some research and it is due to simplifying the complexity that it is derived to o(n) originally this algo is O(N+N/2)
This being O(N) is the biggest mathematical hoax in my opinion.
Bro is not sure what he is teaching, must have practiced what he is teaching before, he takes so many gaps of time to confirm what to speak now which makes me unsure whether he is teaching even right or not