การหา LCP ของสองสายในเวลาคงที่และปริภูมิเชิงเส้น

นี่คือปัญหา:
สมมติว่า S คือชุดของสตริง และเราทราบความยาวรวมของสตริงทั้งหมดใน S ใน n เราต้องหาโครงสร้างข้อมูลที่มีช่องว่าง O(n) ที่ค้นหา LCP(s,t) ใน O(1) โดยที่ LCP เป็นคำนำหน้าทั่วไปที่ยาวที่สุดระหว่างสตริง ส,ที.


ตอนแรกฉันคิดว่าสามารถใช้แฮชได้เนื่องจากเราสามารถตรวจสอบตัวเลขในเวลาคงที่และค้นหาสตริงย่อยในเวลาคงที่ได้หากเราแฮชสตริงล่วงหน้า แต่ฉันไม่คิดว่าวิธีนี้จะได้ผลเนื่องจากมันต้องการพื้นที่มากขึ้นและหลังจากนั้นสักครู่ การค้นหา ฉันพบว่าวิธีแก้ปัญหาอาจอยู่ที่การใช้ Trie's, Suffix arrays และอาจเป็น LCA และ RMQ ฉันคิดว่าฉันเกือบจะได้คำตอบแล้ว แต่ไม่รู้ว่าแนวคิดเหล่านี้จะทำงานร่วมกันเพื่อสร้างโครงสร้างข้อมูลที่ให้ LCP ได้อย่างรวดเร็วได้อย่างไร


ขอบคุณสำหรับการอ่าน


prefix algorithm data-structures
person FrastoFresto    schedule 03.01.2020    source แหล่งที่มา
comment
เราสามารถสรุปได้ว่าความยาวของแต่ละสตริงคือ sqrt(n) และมีสตริง sqrt(n) หรือไม่   -  person Yonlif    schedule 03.01.2020
comment
@ Yonlif ฉันไม่คิดอย่างนั้น เราเพิ่งรู้ว่าความยาวรวมของทั้งหมดคือ n   -  person FrastoFresto    schedule 03.01.2020
comment
ฉันกำลังคิดถึงการสลายตัวของแสงอย่างหนักโดยมีสายยาวกว่านั้น sqrt(n)   -  person Yonlif    schedule 03.01.2020
comment
@Yonlif ชอบบีบอัดไตร่ตรองเหรอ?   -  person FrastoFresto    schedule 03.01.2020
comment
s และ t คืออะไร? เพราะหากพวกมันเป็นสตริง คุณจะไม่สามารถจดจำมันได้ในเวลาคงที่ด้วยซ้ำ หากเป็นสิ่งที่สามารถแมปกับโหนดภายในในเวลาคงที่ คุณก็สามารถทำแบบสอบถาม LCA ได้   -  person Matt Timmermans    schedule 03.01.2020
comment
การลองจะทำได้ใน O(length of prefix) เนื่องจากคุณไม่สามารถสร้างสตริงเพื่อส่งคืนเร็วกว่านั้นได้ ฉันคิดว่านี่จะต้องเป็นคำตอบ มีวลีเช่นสตริงที่มีความยาวคงที่อยู่ในคำอธิบายดั้งเดิมหรือไม่   -  person btilly    schedule 03.01.2020
comment
ดังนั้นจึงจะได้รับอนุญาตให้ใช้อะไรก็ได้ O(....) เพื่อ กรอก โครงสร้างข้อมูลนั้นด้วยข้อมูลหรือไม่   -  person Lasse V. Karlsen    schedule 04.01.2020
comment
คำตอบของข้อความนั้นคือ ใช่ นั่นฟังดูเป็นแผนที่ดี! แล้วถ้ามีคนถามว่า โครงสร้างข้อมูลนั้นคืออะไร? ฉันจะตอบกลับไปว่า โอ้ คุณกำลังถามคำถามใช่ไหม? คุณเคยดู Jeopardy บ้างไหม?   -  person Lasse V. Karlsen    schedule 04.01.2020

คำตอบ (1)


arrow_upward
1
arrow_downward

ฉันคิดว่าฉันรู้คำตอบที่พวกเขากำลังมองหา

ขั้นแรก สร้างไทรให้กับสายทั้งหมด แต่ละโหนดใน trie สามารถรวมตัวชี้ไปยังสตริงที่ขึ้นต้นด้วยคำนำหน้านั้นและความยาว แมปแต่ละสตริงกับโหนดสุดท้ายในไตรที่สตริงนั้นต่อกัน

ตอนนี้เมื่อได้รับคู่ของสตริง (ซึ่งสมมุติว่าคุณถูกบอกว่าเป็นสตริง i และสตริง j) ปัญหาในการส่งคืนสตริงคือคำถามในการค้นหาบรรพบุรุษร่วมที่น้อยที่สุด จากนั้นจึงส่งคืนคู่ (pointer_to_start_of_string, length)

แต่ trie สามารถเขียนเป็นต้นไม้ได้และจากนั้น Tarjan ก็มีอัลกอริธึม Common Ancestors ที่ต่ำที่สุดแบบออฟไลน์ (ดู https://www.geeksforgeeks.org/tarjans-off-line-lowest-common-ancestors-algorithm/) สามารถใช้เพื่อประมวลผลแผนผังนั้นล่วงหน้าเพื่อตอบคำถาม LCA ได้อย่างรวดเร็ว .

ในทางเทคนิคแล้วไม่ใช่ O(1) อย่างไรก็ตาม มันคือ O(inverse_ackermann(n)) ซึ่งถือเป็นค่าคงที่ที่ค่อนข้างน้อยสำหรับคอมพิวเตอร์ทุกเครื่องที่เหมาะกับจักรวาลที่สังเกตได้

person btilly    schedule 03.01.2020
comment
LCA ของ Trajan เป็นอัลกอริธึมออฟไลน์ที่ไม่สามารถตอบคำถามเฉพาะบุคคลได้ในขณะนั้น แม้ว่าจะประมวลผลล่วงหน้าแล้วก็ตาม มีวิธีดำเนินการในเวลาคงที่หลังจากประมวลผลล่วงหน้าด้วยสเปซเชิงเส้นโดยใช้ออยเลอร์ทัวร์ชมแผนผังเพื่อลดปัญหาให้เป็นแบบสอบถามขั้นต่ำในช่วง ดู geeksforgeeks.org/find-lca-in-binary- tree-using-rmq และ en.wikipedia.org/wiki/Range_minimum_query - person Matt Timmermans; 04.01.2020