Longest Palindromic Substring in Linear Time with Hashing in Linear Time and Constant Extra Space

Правка en2, от dajeff, 2025-03-12 09:44:10

Many sources note that Longest Palindromic Substring (LPS) can be solved in linearithmic time using hashing and binary search.

Surprisingly, I have not found any sources claiming that LPS can be solved in linear time with hashing, despite such an algorithm being possible and elementary. We'll introduce such an algorithm

Теги hashing, palindrome

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский dajeff 2025-03-12 10:43:41 0 (published)
en7 Английский dajeff 2025-03-12 10:43:07 224 Tiny change: 'cases. If adding `s' -> 'cases. If extending our candidate window by adding `s'
en6 Английский dajeff 2025-03-12 10:37:05 1069
en5 Английский dajeff 2025-03-12 09:52:37 553 Tiny change: 'bbf58f/)\n```cpp\n' -> 'bbf58f/)\n\n```cpp\n'
en4 Английский dajeff 2025-03-12 09:46:17 0
en3 Английский dajeff 2025-03-12 09:46:17 1508
en2 Английский dajeff 2025-03-12 09:44:10 2372
en1 Английский dajeff 2025-02-25 23:01:50 2480 Initial revision (saved to drafts)