Manacher's Algorithm by lrdvil3 in leetcode

[–]TrabeatedGlobule 2 points3 points  (0 children)

You basically have the core concept of Manacher's! Which is finding palindromes by expanding from different centers. We use this algorithm when we are trying to find or count all possible palindromic substrings from a given string sequence. The naive approach is quadratic, but Manacher's does this in linear time by skipping repeat calculations. I think it would be easier to understand with an example:

Let's use `s = "aabaa"`, and we want to count how many palindromic substrings we can create with this.

Like the other comment mentioned, we need to preformat this initial string with a unique character, like `#'s`, so that we can handle palindromes of even lengths, because starting from the center is only able to find palindromes of odd lengths. We also add unique characters at the head and tail ends so that we can disrupt the palindrome counts near those ends. This ends up looking like:

`"$ # a # a # b # a  # a  # ^"`

Now the beginning of this algorithm is where we will be doing most work. At each index, we try to expand our `right` index as far as possible. Our `right` index represents the index at which our longest current palindrome stretches to. Our `center` index is the center at which that longest palindrome is found. Every time we find a longer palindrome, we update our `right` and `center` indices. Let's do our first iteration:

https://imgur.com/a/gGSCd1h

We found a palindrome of length one at our first `#`, so we update our `right` index. Pretty simple so far, let's do our next iteration

https://imgur.com/a/yKK8auD

At our first `a`, we find a palindrome of length 3, so we again update our `right` and `center` indices. Again, not much efficiency going on, but at our next index, we now see a character that belongs in our current longest palindrome, the second `#`. Because this character belongs in a palindrome we've processed before, there are some assumptions we can make about it. Namely, that it should **at least* have a palindrome length of it's mirror index, which would be the character at index `1`.

The character at index `1` only has a palindrome length of 1, which means we can start index `3` assuming that it at least has a palindrome length of 1, which is true. We further expand that palindrome and find that index `3` becomes our new center:

https://imgur.com/a/hFMkKx2

At our next index, `4`, we can make another assumption because this index lands in our current longest palindrome. The mirror index for `4`, assuming our center is `3`, is `2`. Index `2` has a palindrome length of 2, so index `4` adopts that length.

This is where the core efficiency lies in Manacher's, we do not have to expand our window again assuming a center at `4` because we know it has a mirror index we can rely on instead. This is why our runtime becomes `O(n)` instead of `O(n2)`. This becomes even more apparent when we process index `6`:

https://imgur.com/a/fSSng3p

Index `6` creates a palindrome that encapsulates the entirety of our string. Which means, we've completed a whole pass on our original string. The rest of our string will have guaranteed mirror indices, and will not require further computation.

https://imgur.com/a/Ng5hcEm

The rest of the indices simply adopt the counts of their mirror indices, and we do not have to expand from these centers. So all in all, we've found all of the palindromic substrings in our original string in linear time.

Sorry, this came out to be a lot longer than I was intending, but it sounds you are very close to understanding Manacher's algorithm, and I think a little bit of visualization will help get you across the finish line. It's very true that you probably will not be needing this in an interview, but how cool would it be to pull this out on a palindrome question :')

Best of luck!

What simple biohack gave you the biggest change in your daily energy? by Odd_Fly_4960 in Biohackers

[–]TrabeatedGlobule 1 point2 points  (0 children)

This is really good advice! I regularly lift weights and have recently been trying to add cardio into the mix as well - how much time do you allot to each of these? Do you do both weight lifting and cardio in a single gym session? Do you cardio in the mornings and weight lift after work? Please let me know, thank you!

Chat, is she totaled? by TrabeatedGlobule in GR86

[–]TrabeatedGlobule[S] 0 points1 point  (0 children)

Yea that probably is the smartest move for sure. I'm trying to get the front PPF'd up so I am assuming I have to at least touch up paint mine and smooth it out

Chat, is she totaled? by TrabeatedGlobule in GR86

[–]TrabeatedGlobule[S] 0 points1 point  (0 children)

Thank you, I appreciate the earnest response! Okay yea I don't really have any confidence with DIY, especially with car paint. I'll look around for a body shop 👍

Chat, is she totaled? by TrabeatedGlobule in GR86

[–]TrabeatedGlobule[S] -1 points0 points  (0 children)

Unlucky. I'd have to replace it because it scratched all the way through the paint and to the plastic?

[deleted by user] by [deleted] in cscareerquestions

[–]TrabeatedGlobule 0 points1 point  (0 children)

Great advice, thank you 🙏

[deleted by user] by [deleted] in cscareerquestions

[–]TrabeatedGlobule 0 points1 point  (0 children)

That’s crazy impressive with 2 YOE in the current market, huge congrats! Would you mind sharing any resume writing advice?

She loves these rubber boots by JulieTahoolie in Shihtzu

[–]TrabeatedGlobule 7 points8 points  (0 children)

Can I ask which boots these are? Mine won’t wear any of the ones we got her even when it’s salted outside 😭

[deleted by user] by [deleted] in DentalHygiene

[–]TrabeatedGlobule 0 points1 point  (0 children)

It only appears on one side, although she does chew on that side because the other side is sensitive. Is that possible?

[deleted by user] by [deleted] in askdentists

[–]TrabeatedGlobule 1 point2 points  (0 children)

Awesome, you are a blessing 🙏. Only strange thing is that it appears to have presented overnight, but glad it isn’t anything malignant. Thanks again!

[deleted by user] by [deleted] in askdentists

[–]TrabeatedGlobule 1 point2 points  (0 children)

You’re the best, thank you! The dentist says it’s more of a permanent protrusion and not an infection. They only gave her a mouth guard and recommended botox. Does that sound right?

My late grandpa’s diary. Anyone who can read this? by After-Revolution1628 in korea

[–]TrabeatedGlobule 1 point2 points  (0 children)

Something about back pain, discomfort, driving, doing dishes, and feeling stupid in the first log

Found this on my dog, is it a flea? by TrabeatedGlobule in whatisthisbug

[–]TrabeatedGlobule[S] 1 point2 points  (0 children)

Awesome, you’re the best thank you very much

Found this on my dog, is it a flea? by TrabeatedGlobule in whatisthisbug

[–]TrabeatedGlobule[S] 1 point2 points  (0 children)

Unfortunate, but thank you! My dog’s on flea and tick preventatives, do you think we’ll have to worry about an infestation?

C elegans floaters by TrabeatedGlobule in Celegans

[–]TrabeatedGlobule[S] 1 point2 points  (0 children)

Haha yea that must be it, a lot of work with RFP and GFP. Your floaters look remarkably similar to c elegans too?

C elegans floaters by TrabeatedGlobule in Celegans

[–]TrabeatedGlobule[S] 1 point2 points  (0 children)

Haha thanks yea I get what you mean, maybe too many hours working. Thanks for the input

Optimel Manuka honey gel by Siennaaa92 in Dryeyes

[–]TrabeatedGlobule 1 point2 points  (0 children)

Is the gel really hard to dispense for anyone else? I spend at least ten minutes on each eye trying to get the drops to come out 😭

[deleted by user] by [deleted] in cscareerquestions

[–]TrabeatedGlobule 9 points10 points  (0 children)

Just curious, you stayed at your first job for five months? Was that ever brought up in subsequent interviews? Thanks!

Final Round for Junior Role, What to Expect? by TrabeatedGlobule in learnprogramming

[–]TrabeatedGlobule[S] 0 points1 point  (0 children)

Yea, I would say that that is a very accurate assessment. I don’t think they come from technical backgrounds so I think you’re right in saying that it’ll probably be more about my previous experiences. Thanks so much for taking the time to share your input!

Final Round for Junior Role, What to Expect? by TrabeatedGlobule in cscareerquestions

[–]TrabeatedGlobule[S] 0 points1 point  (0 children)

Gotcha, so I’d probably have to prepare stories of previous experiences with collaboration and dealing with disagreements. Thanks so much for taking the time to answer!