KarimElSheikh's blog

By KarimElSheikh, history, 6 years ago, In English

Is it possible to extend Manacher's algorithm to include information about the longest palindromic substring that starts at every position and still keep the O(N) time complexity?

For example the string cbcbaaabc should give the array [3, 3, 7, 5, 3, 2, 1, 1, 1] which corresponds to the strings cbc, bcb, cbaaabc, baaab, aaa, aa, a, b, c respectively

What about an O(NlogN) solution?

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

By KarimElSheikh, history, 9 years ago, In English

I can't resolve this compilation error http://codeforces.com/contest/497/submission/11686183 It compiles fine on my PC

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By KarimElSheikh, history, 9 years ago, In English

There are some few problems I came across like Fish and Virus synthesis which seem to have solutions with BFS traversal and typical DP minimization/maximization function. I want to practice this technique because normally when I think of coding a DP solution I only think of DFS traversal, any ideas of problems which are best solved using this technique?

EDIT: Just a clarification this DP style is usually a "Reverse" BFS Traversal of the states where we travel from the leaf nodes upwards level by level and converge to the final state

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it