Problem on article Manacher's Algorithm - Finding all sub-palindromes in O(N) #1372
Assignees
Comments
|
I'm not really convinced this is an issue. If anything, the z algorithm article should be changed to have a similar line as the z algorithms is quite analogous to manacher's algorithm. |
|
It seems to get AC on Library Checker with this change. I don't remember why I put it there in the first place, so I will double-check and update the article if everything is really fine with it. |
I guess if "l" had been initialized with 0, then it could've lead to a negative index. As it is initialized with 1, we're saved. Correct me if I'm wrong though. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Article: Manacher's Algorithm - Finding all sub-palindromes in O(N)
Problem:
Below line ->
p[i] = max(0, min(r - i, p[l + (r - i)]));in manacher_odd function, is max(0, ..) check really required?
As I tried some examples on paper, it seemed every time, the least value of p[i] = min(r - i, p[l + (r - i)]) is 0, so, can we write directly,
p[i] = min(r - i, p[l + (r - i)]);The text was updated successfully, but these errors were encountered: