Temukan semua kemungkinan substring dengan cara tercepat [duplikat]

Untuk String A = "abcd" maka jawabannya seharusnya

{a,ab,abc,abcd,b,bc,bcd,c,cd,d}

Untuk menemukan semua substring saya menggunakan metode berikut

for (int i = 0; i < A.length(); i++) {
    for (int j = i+1; j <= A.length(); j++) {
        System.out.println(A.substring(i,j));
    }
}

Namun menurut pemahaman saya, kompleksitasnya mencapai O(N^2). Bisakah kita membuatnya lebih cepat? Saya merujuk pertanyaan sebelumnya dan ada tautan untuk suffix tree tetapi sepertinya tidak menyelesaikan masalahku. Output yang saya dapatkan dari suffix tree adalah

{
 1: abcd
 2: bcd
 3: cd
 4: d
}

Adakah yang bisa membantu saya menemukan cara tercepat untuk melakukan ini? Sesuatu seperti dalam waktu linier?


java performance substring algorithm time-complexity
person user2228588    schedule 31.03.2013    source sumber
comment
Anda tidak mungkin membuatnya lebih cepat dari O(n^2) untuk membuat daftar titik awal dan akhir dari setiap substring yang mungkin, karena ada O(n^2) substring seperti itu! Jika Anda ingin mencetak setiap substring secara penuh (seperti yang sedang Anda lakukan), maka kompleksitas waktu akan naik menjadi O(n^3) karena dibutuhkan waktu yang sebanding dengan panjang keseluruhan string untuk mencetak setiap substring.   -  person j_random_hacker    schedule 31.03.2013
comment
Perhatikan juga bahwa string kosong juga merupakan substring yang valid.   -  person Philip    schedule 31.03.2013
comment
Anda hanya dapat membuatnya lebih cepat jika Anda akan menjalankan kueri pada kumpulan substring yang tidak menyentuh semuanya. Mencetaknya menyentuh semuanya. Jika Anda ingin bertanya, katakanlah, substring terpanjang apa yang muncul setidaknya dua kali atau substring mana yang lebih dari k karakter paling sering muncul, maka Anda dapat melakukannya tanpa menyebutkan semua substring (dengan pohon sufiks).   -  person harold    schedule 31.03.2013
comment
baris for (int j = i+1; j <= A.length(); j++) harus diubah menjadi for (int j = i+1; j <= A.length() - i; j++)   -  person HojjatK    schedule 09.06.2019

Jawaban (1)


arrow_upward
51
arrow_downward

Anda tidak dapat membuat O(N^2) string dalam waktu lebih baik dari O(N^2). Ini adalah sebuah kemustahilan matematis. Meskipun pembuatan string memerlukan satu instruksi, itu masih merupakan perhitungan O(N^2).

Mengesampingkan kerumitan, menurut saya kode Anda tidak dapat diperbaiki secara signifikan.

Bisakah kita membuatnya lebih cepat?

Mungkin tidak.

Mengoptimalkan potongan kode khusus ini adalah aktivitas yang sia-sia. Karena Anda menulis string ke keluaran standar, kinerja sebenarnya akan didominasi oleh biaya penulisan karakter ... dan apa pun yang dilakukan OS dengan keluarannya.

person Stephen C    schedule 31.03.2013