Longest Square Substring in subquadratic time?

Правка en1, от catalystgma, 2023-07-12 20:16:50

Hello,

I wanted to ask if anybody knows about a subquadratic time complexity algorithm for figuring out the longest square substring of a string $$$s$$$. (i.e. $$$tt = ?$$$ s.t $$$\exists \, u, v$$$ s.t $$$s = uttv$$$, $$$|t|$$$ is maximized)

For example, if:

  • s = mississippi, tt = ssissi or tt = ississ.

  • s = aaaaa, tt = aaaa.

  • s = bababooey, tt = baba.

  • s = foopoopoofoo, tt = poopoo.

The related problem is much better documented (Longest Square Subsequence).

Sorry if the answer is trivial/known. Thank you for your help.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский catalystgma 2023-07-12 20:16:50 640 Initial revision (published)