codinghermit05's blog

Need a list of good algorithms which actually beats DP (Manacher's Algorithm is CRAZY! Please help)
By codinghermit05, 3 months ago, In English

Recently I got to know about this O(n) solution for longest palindromic substring and am stunned by the working of the algorithm. How could an algorithm work better than a grid DP solution?! Would be nice if anyone could break down the algorithm for me. Also looking forward to know about more such daring algorithms that can beat the crap out of the traditional dynamic programming solutions. Thank you.

 
 
 
 
  • Vote: I like it
  • -27
  • Vote: I do not like it

»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Dijkstra's Shortest Path Algorithm (Greedy) | Time Complexity: O(ELogV + VLogV)

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I never learned Manacher's algorithm. I always used hashing. Hash the string forwards and backwards and then compare.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please share your approach/code using the hashing?

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hash the string forward, so like abcd and then hash backwards on dcba.

      → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Using suffix arrays, Longest Common Substring for 2 strings can be solved in O(nlogn) instead of O(n2) DP, and also it performs drastically better for more number of strings.

→ Reply