สตริงย่อย

จากวิกิพีเดีย สารานุกรมเสรี
ข้ามไปที่การนำทาง ข้ามไปที่การค้นหา
" string " เป็นสตริงย่อยของ " substring "

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

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

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

สตริงย่อย

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

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

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

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

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

คำนำหน้า

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

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

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

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

คำต่อท้าย

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

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

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

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

เส้นขอบ

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

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

superstringของเซต จำกัด ของ strings เป็นสตริงเดียวที่มีทุกสตริงใน เป็นสตริงย่อย ตัวอย่างเช่น, เป็นซุปเปอร์สตริงของ , และ เป็นอันที่สั้นกว่า โดยทั่วไป มีความสนใจในการหา superstrings ที่มีความยาวน้อยที่สุด [ ต้องการคำชี้แจง ]การต่อสายอักขระทั้งหมดของ ในลำดับใด ๆ ให้ superstring เล็กน้อยของ . สตริงที่มีการเปลี่ยนแปลงทุกเป็นไปได้ของชุดอักขระที่ระบุเรียกว่าsuperpermutation

ดูเพิ่มเติม

อ้างอิง

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

ลิงค์ภายนอก

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