Diberikan dan string, apakah salah satu dari mereka adalah substring dari yang lain?

Misalkan kita diberi koleksi string, . Saya ingin tahu apakah salah satu dari string tersebut adalah substring dari string lain dalam koleksi. Dengan kata lain, saya ingin algoritma untuk tugas berikut: $n$ $S_1,\dots,S_n$

Input: $S_1,\dots,S_n$

Output: sehingga adalah substring dari dan , atau None jika tidak ada ada $i,j$ $S_i$ $S_j$ $i\ne j$ $i,j$

Apakah ada algoritma yang efisien untuk ini?

Jika kita mengganti "substring" dengan "awalan", ada algoritma yang efisien (mengurutkan string, lalu melakukan pemindaian linier untuk membandingkan string yang berdekatan; pengurutan akan memastikan bahwa substring berbatasan). Tetapi tampaknya lebih menantang untuk menguji apakah string adalah substring dari string lain. Algoritma naif adalah untuk mengulangi semua pasangan $i,j$ , tetapi ini membutuhkan tes substring $\Theta(n^2)$ . Apakah ada algoritma yang lebih efisien?

Saya kira kita bisa menyebut ini "all-pair substring testing", atau sesuatu seperti itu.

Tujuan utama saya adalah memangkas koleksi sehingga tidak ada string yang merupakan substring dari yang lain, dengan menghapus masing-masing yang merupakan substring dari sesuatu yang lain dalam koleksi.

Petunjuk: Susunan sufiks.

Nama samaran

Sebagai catatan tambahan, tidak benar jika Anda menghapus substring saat Anda menemukannya. Itu akan lebih sedikit. Anda juga harus mengurutkan berdasarkan panjang karena string yang lebih panjang tidak dapat muncul dalam string yang lebih pendek. Lagi salah di sini.

Θ (n^{2})

$\Theta(n^2)$

Θ (n^{2})

$\Theta(n^2)$

Alexis Wilke

@AlexisWilke, benar: itulah jumlah tes substring dalam kasus terburuk (kasus terburuk adalah di mana tidak ada string yang merupakan substring dari yang lain). Mengurutkan berdasarkan panjang hanya memberi Anda faktor dua, yang tidak memengaruhi asimptotik.

Θ (n^{2})

$\Theta(n^2)$

Jawaban:

Anda dapat membangun pohon sufiks dalam waktu linier dan memeriksa apakah ada simpul dalam yang terkait dengan string penuh (waktu konstan per simpul).

Secara lebih rinci, anggap kita diberi string . $s_1, \dots, s_n \in \Sigma^*$

Buat pohon sufiks (umum) dari dengan penanda terminal berbeda berpasangan . $s_1\$_1, s_2\$_2, \dots, s_n\$_n$ $n$ $\$_1,\dots,\$_n \notin \Sigma$

Menggunakan algoritma Ukkonen , ini dapat dilakukan dalam waktu linier; linear dalam jumlah semua panjang string.
Dengan asumsi bahwa Anda memberi label daun dengan jika mereka mewakili akhiran dari $(i,j)$ $s_i[j..|s_i|]$ , lintasi pohon dan temukan daun yang berlabel , yaitu daun yang sesuai dengan string penuh. $s_i$ $n$ $(i,0)$

Ini membutuhkan waktu linier dalam ukuran pohon, yang itu sendiri linier dalam ukuran input.
Daun turunan dari induk (yang dicapai oleh tepi berlabel ) mewakili semua kecocokan dari set; ini mengikuti dari invarian dasar pohon suffix. Temukan satu kecocokan dengan turun ke daun apa pun (tapi ). $(i,0)$ $\$_i$ $(i,0)$

Ini lagi membutuhkan waktu linier.

Penanda terminal yang berbeda tidak benar-benar diperlukan; satu yang digunakan untuk mengakhiri semua string cukup memadai selama Anda mengizinkan beberapa label per daun.

Raphael
sumber