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
ortt = 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.