Random LC Things

Random things I’ve found during leetcode. This serves as a list of things I should either try to understand, or I finally did end up understanding. I’ll try to put the description of those things here.

1. From this comment on a leetcode of the day
   1. KMP algorithm for finding a prefix in another string
   2. Z-algorithm, another pattern search algo
   3. Rabin-Karp algorithm, another string searching algo related to rolling hashes, which I swear I learned about at some point in college but now I don’t remember…
2. From LC 2429:
   1. To unset the rightmost bit, use the following: x | (x - 1)
   2. To set the rightmost bit, use the following: x & (x + 1)
   3. This stuff feels like magic, but it makes a lot of sense when you work through the examples. To get an intuition of it, just write down a couple of examples and try it out