ค้นหาสตริงย่อยที่เป็นไปได้ทั้งหมดด้วยวิธีที่เร็วที่สุด [ซ้ำกัน]

สำหรับ String A = "abcd" คำตอบควรเป็น

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

เพื่อค้นหาสตริงย่อยทั้งหมดที่ฉันใช้วิธีการต่อไปนี้

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

แต่ตามความเข้าใจของฉัน ความซับซ้อนไปที่ O(N^2) เราจะทำให้เร็วขึ้นได้ไหม? ฉันอ้างถึงคำถามก่อนหน้านี้และมีลิงก์สำหรับ suffix tree แต่ดูเหมือนจะไม่ แก้ปัญหาของฉัน ผลลัพธ์ที่ฉันได้รับจากทรีต่อท้ายคือ

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

ใครก็ได้โปรดช่วยฉันหาวิธีที่เร็วที่สุดในการทำเช่นนี้? บางอย่างเช่นในเวลาเชิงเส้น?


java performance substring algorithm time-complexity
person user2228588    schedule 31.03.2013    source แหล่งที่มา
comment
คุณไม่สามารถทำให้มันเร็วกว่า O(n^2) เพื่อแสดงรายการจุดเริ่มต้นและจุดสิ้นสุดของแต่ละสตริงย่อยที่เป็นไปได้ เนื่องจากมีสตริงย่อย O(n^2) ดังกล่าว! หากคุณต้องการพิมพ์แต่ละสตริงย่อยทั้งหมด (ดังที่คุณกำลังทำอยู่) ความซับซ้อนของเวลาจะสูงถึง O(n^3) เนื่องจากต้องใช้เวลาเป็นสัดส่วนกับความยาวสตริงโดยรวมในการพิมพ์แต่ละสตริงย่อย   -  person j_random_hacker    schedule 31.03.2013
comment
โปรดทราบว่าสตริงว่างก็เป็นสตริงย่อยที่ถูกต้องเช่นกัน   -  person Philip    schedule 31.03.2013
comment
คุณสามารถทำให้มันเร็วขึ้นได้ก็ต่อเมื่อคุณจะเรียกใช้คิวรีเหนือชุดสตริงย่อยที่ไม่ได้ครอบคลุมทั้งหมด การพิมพ์สัมผัสได้ทั้งหมด หากคุณต้องการถาม เช่น สตริงย่อยที่ยาวที่สุดที่ปรากฏอย่างน้อยสองครั้งคืออะไร หรือสตริงย่อยใดที่มีอักขระมากกว่า k ตัวเกิดขึ้นบ่อยที่สุด คุณสามารถทำได้โดยไม่ต้องระบุสตริงย่อยทั้งหมด (ด้วยแผนผังส่วนต่อท้าย)   -  person harold    schedule 31.03.2013
comment
บรรทัด for (int j = i+1; j <= A.length(); j++) ควรเปลี่ยนเป็น for (int j = i+1; j <= A.length() - i; j++)   -  person HojjatK    schedule 09.06.2019

คำตอบ (1)


arrow_upward
51
arrow_downward

คุณไม่สามารถสร้างสตริง O(N^2) ในเวลาที่ดีกว่า O(N^2) ได้ มันเป็นความเป็นไปไม่ได้ทางคณิตศาสตร์ แม้ว่าการสร้างสตริงจะใช้คำสั่งเดียว แต่นั่นยังคงเป็นการคำนวณ O(N^2)

นอกเหนือจากความซับซ้อนแล้ว ฉันไม่คิดว่าโค้ดของคุณสามารถปรับปรุงให้ดีขึ้นได้อย่างมีนัยสำคัญใดๆ

เราจะทำให้เร็วขึ้นได้ไหม?

อาจจะไม่.

การเพิ่มประสิทธิภาพโค้ดชิ้นนี้ถือเป็นกิจกรรมที่ไร้ประโยชน์ เนื่องจากคุณกำลังเขียนสตริงไปยังเอาต์พุตมาตรฐาน ประสิทธิภาพที่แท้จริงจะถูกครอบงำโดยค่าใช้จ่ายในการเขียนอักขระ ... และอะไรก็ตามที่ระบบปฏิบัติการทำกับเอาต์พุต

person Stephen C    schedule 31.03.2013