こちらです。これを解くアルゴリズムの一つとして下記があります。
Kolpakov, Roman, and Gregory Kucherov. "Finding maximal repetitions in a word in linear time." In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pp. 596–604. IEEE, 1999.
これをする過程で s-factorization というのが出てくるのですが、ABC-EF くらいの文字列アルゴリズムの例題としてよさそうな気がしたので紹介です。
導入
run というのは、ランレングス圧縮 (RLE) のランと同じで、繰り返しを意味する用語です。
$\gdef\ttstr#1{\text{\texttt{#1}}}$
上記の論文中では run という言い回しはされていなくて、repetition と呼ばれています。 長さ $n$ の文字列 $w = a_0a_1\dots a_{n-1}$ の周期とは、任意の $p\le i\lt n$ に対して $a_{i-p} = a_i$ を満たすような最小の正整数 $p$ を指します。 たとえば、$\ttstr{aaaa}$ の周期は $1$、$\ttstr{abcabca}$ の周期は $3$、$\ttstr{abcbc}$ の周期は $5$ です。$n$ が $p$ の倍数になっている必要はないことに注意してください。
文字列 $w = a_0a_1\dots a_{n-1}$ と、非負整数 $k, r$ ($0\le r\lt n$) に対して、 $$w^{k+r/n} = \underbrace{ww\ldots w}_{k\text{ times}}\, a_0a_1\dots a_{r-1}$$ と定義します。$|w^{k+r/n}| = |w|\cdot(k+r/n) = nk+r$ であることに気づいておきます。
一般に、$w^{e/n} = w^{\floor{e/n} + (e\bmod n)/n}$ とします。指数部は、$n$ を分母とする非負の分数に対して定義されるものとします。
長さ $n$ の文字列 $w$ が、ある文字列 $s$ と非負整数 $k$ を用いて $w = s^{2+k/n}$ と書けるとき、$w$ を repetition と呼びます。 たとえば、$\ttstr{abcabca} = \ttstr{abc}^{7/3}$ と書けるので $\ttstr{abcabca}$ は repetition です。$\ttstr{abcab}$ は repetition ではありません。
与えられた文字列 $s$ の部分文字列のうち、repetition であるものを全て列挙することを考えます。 ただし、部分文字列は文字列としてではなく添字の選び方として区別することにします。
しかし、$s = \ttstr{a}^n$ を考えると、$s$ の長さ $2$ 以上の部分文字列全てが repetition であり、最悪 $\Theta(n^2)$ 個の repetition が存在することになります。 これは「列挙してください」という問題に対して相性が悪いです（愚直にやってもよいことになってしまうため）。
そこで、maximal という概念を導入します。 $s = a_0a_1\dots a_{n-1}$ の部分文字列 $s_{l, r} = a_l\dots a_{r-1}$ が maximal repetition であるとは、$s_{l, r}$ の周期 $p\ge 2$ に対して、$s_{l-1, r}$ または $s_{l, r+1}$ が $p$ より大きい周期を持つ（または $l-1\lt 0$ または $r\ge n$ が成り立つ）ことを言います。 maximal repetition は $O(n)$ 個しかないことが示されている（これ難しいです）ので、これであれば $O(n)$ 時間で列挙できる可能性があるわけです。
mississippi における maximal repetition の列挙は次のようになります。
mississippi
~~~~~~~ # (iss)^{7/3}
~~ # (s)^2
~~ # (s)^2
~~ # (p)^2
以下において、文字列や文字同士の連結を $\concat$ で表します。$\ttstr{ab}\concat\ttstr{c} = \ttstr{abc}$ などです。
s-factorization
文字列 $w = a_0a_1\dots a_{n-1}$ の s-factorization とは、$w = u_0u_1\dots u_{k-1}$ なる文字列の列 $(u_0, u_1, \dots, u_{k-1})$ であって、次のように構成されるものです。ただし、各 $u_i$ を factor と呼びます。便宜上、先頭 $i$ 個の factor の長さを $k_i = |u_0\dots u_{i-1}|$ と表します ($k_0 = 0$)。
手順：先頭 $i$ 個の factor $a_0\dots a_{k_i-1}$ に文字 $a_{k_i}$ が含まれないとき、$u_i = w_{k_i}$ とします（1 文字のみからなる文字列）。 そうでないとき、$u_i$ は次の条件を満たす最大の $m$ を用いて $u_i = a_{k_i}\dots a_{k_i+m-1}$ とします ($|u_i| = m$)。
条件：$a_{k_i}\dots a_{k_i+m-1}$ は、$a_0\dots a_{k_i+m-2}$ の部分文字列である。
直感的に言えば、「$u_i$ は $u_0\dots u_i$ に（overlap を許容して）2 回以上現れる」とか「$u_i$ は $a_0\dots a_{k_i-2}$ に 1 回以上現れる」のような感じです。 たとえば、$\ttstr{abaabbabaaba} = (\ttstr{a}, \ttstr{b}, \ttstr{a}, \ttstr{ab}, \ttstr{ba}, \ttstr{baab}, \ttstr{a})$ や $\ttstr{aaaaa} = (\ttstr{a}, \ttstr{aaaa})$ です。
解法
さて、これを求めていきます。
$\gdef\prefix#1#2{{#1[\ldots#2]}}$ $\gdef\suffix#1#2{{#1[#2\ldots]}}$ $\gdef\lcp{\operatorname{lcp}}$
文字列 $w = w_0w_1\dots w_{n-1}$ に対して、接頭辞 $j$ を $\prefix wj = w_0\dots w_{j-1}$、接尾辞 $j$ を $\suffix wj = w_j\dots w_{n-1}$ で定義します。$0\le j\le n$ に対して $w = \prefix wj\concat\suffix wj$ が成り立ちます。
また、文字列 $s$ と $t$ の最長共通接頭辞 (LCP) の長さを $\lcp(s, t)$ と書きます。$m = \lcp(s, t)$ としたとき、$\prefix sm = \prefix tm$ かつ、$\prefix s{m+1}\ne \prefix t{m+1}$（または $m+1\gt |s|$ または $m+1\gt |t|$）を満たします。
$u_i$ の構成の手順のうち後者の方（それより前の factor に $w_{k_i}$ が含まれる方）の条件を言い換えます。 $j\lt k_i$ に対して $\suffix wj$ と $\suffix w{k_i}$ の最長共通接頭辞の長さを $m_j$ とするとき、$|u_i| = \max_j m_j$ となります。
というわけで、以下のクエリを処理できればよいことになります。
長さ $n$ の文字列 $w$ が与えられるので、各 $0\lt i\lt n$ に対して下記を求めてください。 $$ \max_{0\le j\lt i} \lcp(\suffix wj, \suffix wi). $$
これは suffix array と LCP array を用いて答えられます。 suffix array において、接尾辞 $i$ に近い方が LCP が長いことから、接尾辞 $i$ から最も近くにある接尾辞 $j$ ($j\lt i$) をなんとかして探し、それとの LCP を計算すればいいことになります。
これは、適切にスタックを管理しながら suffix array を昇順（・降順）に走査することで、$i$ から左側（・右側）に最も近い $j$ を $O(n)$ 時間で探すことができます（そうした $j$ が存在しないケースには注意）。
(0, ..., n-1) の順列 (p_0, ..., p_{n-1}) が与えられます。各 0 ≦ i < n に対して、「j < i かつ p_j < p_i を満たす最大の j（存在しなければその旨）」を求めてください（全体で O(n) 時間で）
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) September 15, 2023
i昇順にstackでp_iより小さいものが出てくるまでpopしてp_iをpushですか
— tute (@tute7627) September 15, 2023
アルファベットサイズが $n^{O(1)}$ であれば、suffix array は SA-IS を用いて $O(n)$ 時間で構築できます。 LCP array や RMQ も $O(n)$ 時間で構築できるので、全体で $O(n)$ 時間でクエリ処理できます。
クエリの答えが $0$ だったとき、s-factorization の構成手順で言うところの前者の方になることに注意すると、s-factorization を $O(n)$ 時間で求められたことになります。
s-factorization 以外
s-factorization を求めた後は、次のような問題を解かされます。
文字列 $t = t_0t_1\dots t_{m-1}$ と $u = u_0u_1 \dots u_{n-1}$ が与えられます。 各 $1\le i\le n$ に対して、$t$ と $t\concat \prefix ui$ の最長共通接尾辞の長さを求めてください。
全体で $O(m+n)$ 時間でお願いします。
この $t$, $u$ は s-factorization に基づいて構成される文字列ですが、これを解く上では s-factorization の性質を使うわけではないので、一旦忘れても問題ありません。
解法
$\gdef\rev{\operatorname{rev}}$
求めたいものは、 $$ \begin{aligned} &\phantom{{}={}} {\lcp}(\rev(t), \rev(t\concat\prefix ui)) \\ &= {\lcp}(\rev(t), \rev(\prefix ui)\concat \rev(t)) \end{aligned} $$ と言い換えられます。ここで、 $$ \rev(\prefix u{i+1})\concat \rev(t) = u_i\concat\rev(\prefix ui)\concat \rev(t) $$ であることに注意すると、$\rev(u)\concat\rev(t)$ の各接尾辞に対して、$\rev(t)$ との LCP を求めればよいことがわかります。
よって、$t$ にも $u$ にも現れない文字 $\bot$ を用いて $\rev(t) \concat \bot \concat \rev(u) \concat \rev(t)$ を構成し、それに対して Z algorithm を適用すればよいです。
提出
所感
文字列界隈の線形時間アルゴリズム天才がち。
競プロ頻出のやつは「ふつう」みたいな感想になってきますが、あまり出てこないやつを調べるとびっくりしがちです。
s-factorization を求めてどうするのかとか、所望のものが線形個しかないことの証明とかは論文を読んでほしいですが、記事中で紹介した部分は ABC-E から F くらい（勝手なイメージで 450–475 くらい？）な気がするので、文字列アルゴリズムに苦手意識のある人は練習として解いてみるといい気がします。
おわり
おわりです。
