Temukan pola berulang terpanjang dalam sebuah string

Saya mencari algoritma yang efisien untuk menemukan pola berulang terpanjang dalam sebuah string.

Misalnya, perhatikan string angka berikut:

5431428571428571428571428571427623874534.

Seperti yang Anda lihat, 142857142857adalah pola terpanjang yang diulang beberapa kali (setidaknya dua kali) dalam string ini.

String yang diulang seharusnya tidak mengandung ide apa pun alih-alih kekerasan?

Masalahnya secara mengejutkan adalah non-sepele. Pertama, dua algoritma brute force. Kotak ("pola berulang") diberikan oleh panjangnya $\ell$ dan posisi $p$ , dan membutuhkan waktu $O(\ell)$ untuk memverifikasi. Jika kita membahas semua $\ell$ dan $p$ , kita mendapatkan algoritma $O(n^3)$ . Kita dapat memperbaikinya dengan terlebih dahulu mengulangi $\ell$ , dan kemudian memindai string dengan dua pointer berjalan pada jarak $\ell$ . Dengan cara ini, seseorang dapat memverifikasi apakah kuadrat panjang $2\ell$ ada dalam waktu linier, memberikan total waktu berjalan $O(n^2)$ .

Kolpakov dan Kucherov mengembangkan algoritma untuk menemukan semua pengulangan maksimal dalam kata dalam waktu $O(n)$ [1], dan algoritma mereka dapat digunakan untuk menemukan semua kotak maksimal dalam waktu $O(n)$ . Sebuah ulangi adalah subword dari bentuk $w^kx$ , di mana $k \geq 2$ dan $x$ adalah awalan yang tepat $w$ . Kuadrat terbesar yang terkandung dalam pengulangan itu adalah $(w^{\lfloor k/2 \rfloor})^2$. Menggunakan rumus ini, mengingat semua pengulangan maksimal dalam sebuah kata (yang hanya ada $O(n)$ banyak), orang dapat menemukan kuadrat terbesar.

[1] Kolpakov, R., & Kucherov, G. (1999). Menemukan pengulangan maksimal dalam sebuah kata dalam waktu linier . Dalam Yayasan Ilmu Komputer, 1999. Simposium Tahunan ke-40 tentang (hal. 596-604). IEEE.