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.