Proof. The idea is the same as in L

Proof. The idea is the same as in Lemma 3: for each vertex of the suffix tree we
construct a structure containing all its ancestors sorted according to their depths. Note that
the depths are smaller than M so we can apply Lemma 4. The total
construction time is O(M × M < ) = O(M 1+< ) and answering a query reduces to one predecessor
lookup. ✷

ผลลัพธ์ (ไทย) 1:

หลักฐานการ มีความคิดเดียวกับการจับมือ 3: สำหรับแต่ละจุดของ suffix ต้นไม้เรา
สร้างโครงสร้างที่ประกอบด้วยบรรพบุรุษเรียงลำดับตามความลึกของพวกเขา หมายเหตุว่า
ลึกมีขนาดเล็กกว่า M ดังนั้นเราสามารถใช้การจับมือ 4 รวม
ก่อสร้างเวลาเป็น O (M × M <) = O(M 1 <) และตอบแบบสอบถามลดไปหนึ่งรุ่นก่อน
ค้นหา ✷

ผลลัพธ์ (ไทย) 2:

หลักฐาน ความคิดที่เป็นเช่นเดียวกับในบทแทรกที่ 3: สำหรับจุดสุดยอดของต้นไม้ su FFI x แต่ละที่เรา
สร้างโครงสร้างที่มีทั้งหมดบรรพบุรุษแยกตามระดับความลึกของพวกเขา ทราบว่า
ระดับความลึกที่มีขนาดเล็กกว่า M เพื่อให้เราสามารถใช้บทแทรก 4 รวม
ระยะเวลาการก่อสร้างเป็น O (M × M <) = O (M 1+ <) และตอบแบบสอบถามลดไปก่อนหน้านี้หนึ่ง
ค้นหา ✷

ผลลัพธ์ (ไทย) 3:

พิสูจน์ ความคิดเหมือนกับในแทรกที่ 3 : สำหรับแต่ละจุดยอดของซูffi X ต้นไม้เรา
สร้างโครงสร้างที่มีบรรพบุรุษของมันทั้งหมดเรียงตามระดับความลึกของพวกเขา หมายเหตุ
ลึกมีขนาดเล็กกว่าเมตร เพื่อให้เราสามารถใช้รูปแบบ 4 เวลาก่อสร้างรวม
O ( m × m < ) = O ( M 1 < ) และตอบแบบสอบถามลดไปหนึ่งปี
การค้นหา ✷