สตริงย่อย

ในทฤษฎีภาษาอย่างเป็นทางการและวิทยาศาสตร์คอมพิวเตอร์ที่ย่อยเป็นลำดับต่อเนื่องกันของตัวละครภายในสตริง ตัวอย่างเช่น " the best of " เป็นสตริงย่อยของ " It was the best of times " สิ่งนี้ไม่ควรสับสนกับsubsequenceซึ่งเป็นลักษณะทั่วไปของสตริงย่อย ตัวอย่างเช่น " Itwastimes " เป็นผลสืบเนื่องของ " It was the best of times " แต่ไม่ใช่สตริงย่อย

" string " เป็นสตริงย่อยของ " substring "

คำนำหน้าและส่วนต่อท้ายเป็นกรณีพิเศษของสตริงย่อย คำนำหน้าของสตริง $S$ เป็นสตริงย่อยของ $S$ ที่เกิดขึ้นตอนต้นของ $S$ ; ในทำนองเดียวกันคำต่อท้ายของสตริง $S$ เป็นสตริงย่อยที่เกิดขึ้นที่ส่วนท้ายของ $S$ .

รายการสตริงย่อยทั้งหมดของสตริง " apple " จะเป็น " apple "," appl "," pple "," app "," ppl ", " ple ", " ap ", " pp ", " pl ", " le "," a "," p ", " l ", " e ", "" (สังเกตสตริงว่างในตอนท้าย)

สตริงย่อย

สตริง $u$ เป็นสตริงย่อย (หรือปัจจัย) ^[1]ของสตริง $t$ ถ้ามีสองสตริง $p$ และ $s$ ดังนั้น $t=pus$ . โดยเฉพาะอย่างยิ่ง สตริงว่างคือสตริงย่อยของทุกสตริง

ตัวอย่าง: The string $u=$ ana เท่ากับสตริงย่อย (และส่วนต่อท้าย) ของ) $t=$ banana ที่ออฟเซ็ตที่แตกต่างกันสองแบบ:

กล้วย |||||| อานา|| ||| อนา

เกิดขึ้นครั้งแรกกับ $p=$ b และ $s=$ naในขณะที่เกิดขึ้นครั้งที่สองกับ occurrence $p=$ ban และ $s$ เป็นสตริงว่าง

สตริงย่อยของสตริงคือคำนำหน้าของคำต่อท้ายของสตริง และเทียบเท่ากับส่วนต่อท้ายของคำนำหน้า ตัวอย่างเช่นnanเป็นคำนำหน้าของnanaซึ่งเป็นส่วนต่อท้ายของbanana. ถ้า $u$ เป็นสตริงย่อยของ $t$ มันยังเป็นผลสืบเนื่องซึ่งเป็นแนวคิดทั่วไปมากขึ้น เกิดขึ้นของรูปแบบที่กำหนดในสตริงที่กำหนดสามารถพบกับขั้นตอนวิธีการค้นหาสตริง หาสตริงที่ยาวที่สุดซึ่งเท่ากับย่อยของสองคนหรือมากกว่าสตริงเป็นที่รู้จักกันเป็นปัญหาที่พบบ่อยย่อยที่ยาวที่สุด ในวรรณคดีคณิตศาสตร์ สตริงย่อยเรียกอีกอย่างว่าคำย่อย (ในอเมริกา) หรือปัจจัย (ในยุโรป) ^{[ ต้องการการอ้างอิง ]}

คำนำหน้า

สตริง $p$ เป็นคำนำหน้า^[1]ของสตริง $t$ ถ้ามีสตริง $s$ ดังนั้น $t=ps$ . คำนำหน้าที่เหมาะสมของสตริงไม่เท่ากับสตริงตัวเอง; ^[2]บางแหล่ง^[3]นอกจากนี้ ยังจำกัดคำนำหน้าที่เหมาะสมให้ไม่เว้นว่างไว้ คำนำหน้าสามารถเห็นได้ว่าเป็นกรณีพิเศษของสตริงย่อย

ตัวอย่าง: สตริงbanเท่ากับคำนำหน้า (และสตริงย่อยและลำดับย่อย) ของสตริงbanana:

กล้วย|||ห้าม

สัญลักษณ์เซตย่อยสี่เหลี่ยมบางครั้งใช้เพื่อระบุคำนำหน้า ดังนั้น $p\sqsubseteq t$ แสดงว่า $p$ เป็นคำนำหน้าของ $t$ . สิ่งนี้กำหนดความสัมพันธ์แบบไบนารีบนสตริง เรียกว่าความสัมพันธ์ส่วนหน้าซึ่งเป็นลำดับส่วนนำหน้าเฉพาะ

คำต่อท้าย

สตริง $s$ เป็นคำต่อท้าย^[1]ของสตริง $t$ ถ้ามีสตริง $p$ ดังนั้น $t=ps$ . ต่อท้ายที่เหมาะสมของสตริงไม่เท่ากับสตริงตัวเอง ตีความ จำกัด มากขึ้นก็คือว่ามันยังไม่ว่าง[1]คำต่อท้ายสามารถเห็นได้ว่าเป็นกรณีพิเศษของสตริงย่อย

ตัวอย่าง: สตริงnanaเท่ากับส่วนต่อท้าย (และสตริงย่อยและลำดับย่อย) ของสตริงbanana:

กล้วย |||| นานา

ต้นไม้ต่อท้ายสตริงเป็นTrie โครงสร้างข้อมูลที่แสดงทั้งหมดของคำต่อท้ายของมัน ต้นไม้ต่อท้ายมีจำนวนมากของการใช้งานในขั้นตอนวิธีการสตริง อาร์เรย์ต่อท้ายเป็นรุ่นที่เรียบง่ายของโครงสร้างข้อมูลที่รายชื่อตำแหน่งเริ่มต้นของคำต่อท้ายในลำดับเรียงตามตัวอักษรนั้น มันมีแอพพลิเคชั่นเดียวกันมากมาย

ชายแดน

เส้นขอบคือคำต่อท้ายและคำนำหน้าของสตริงเดียวกัน เช่น "bab" คือเส้นขอบของ "babab" (และของ "babooneatingakebab" ด้วย)

ซูเปอร์สตริง

superstringของเซต จำกัด $P$ ของ strings เป็นสตริงเดียวที่มีทุกสตริงใน $P$ เป็นสตริงย่อย ตัวอย่างเช่น, ${\text{bcclabccefab}}$ เป็นซุปเปอร์สตริงของ $P=\{{\text{abcc}},{\text{efab}},{\text{bccla}}\}$ , และ ${\text{efabccla}}$ เป็นอันที่สั้นกว่า โดยทั่วไป มีความสนใจในการหา superstrings ที่มีความยาวน้อยที่สุด ^{[ ต้องการคำชี้แจง ]}การต่อสายอักขระทั้งหมดของ $P$ ในลำดับใด ๆ ให้ superstring เล็กน้อยของ $P$ . สตริงที่มีการเปลี่ยนแปลงทุกเป็นไปได้ของชุดอักขระที่ระบุเรียกว่าsuperpermutation

ดูสิ่งนี้ด้วย

อ้างอิง

^ ^a b c Lotaire, M. (1997). Combinatorics กับคำ . เคมบริดจ์: สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. ISBN 0-521-59924-5.
^ เคลลี่, ดีน (1995). ออโตและเป็นทางการภาษา: บทนำ ลอนดอน: Prentice-Hall International ISBN 0-13-497777-7.
^ กัสฟิลด์, แดน (1999) [1997]. อัลกอริทึมใน Strings, ต้นไม้และลำดับ: วิทยาศาสตร์คอมพิวเตอร์และชีววิทยาเชิงคอมพิวเตอร์ สหรัฐอเมริกา: สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. ISBN 0-521-58519-8.

ลิงค์ภายนอก

สื่อที่เกี่ยวข้องกับSubstringที่ Wikimedia Commons

[Lot97-1] Lotaire, M. (1997). Combinatorics กับคำ . เคมบริดจ์: สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. ISBN 0-521-59924-5.

[Kel95-2] เคลลี่, ดีน (1995). ออโตและเป็นทางการภาษา: บทนำ ลอนดอน: Prentice-Hall International ISBN 0-13-497777-7.

[Gus97-3] กัสฟิลด์, แดน (1999) [1997]. อัลกอริทึมใน Strings, ต้นไม้และลำดับ: วิทยาศาสตร์คอมพิวเตอร์และชีววิทยาเชิงคอมพิวเตอร์ สหรัฐอเมริกา: สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. ISBN 0-521-58519-8.

[1]