متتبّع السلاسل النصية – الفهارس والسلاسل الجزئية وخوارزميات السلاسل

علوم الحاسوبالخوارزميات وحل المشكلات15–16 سنة

استخدمها مع صفي

تُرسم السلسلة النصية صفًّا من خانات المحارف مفهرسة بدءًا من ⁦0⁩. يغطي وضع «عمليات السلاسل» الدمج، والطول، والمحرف عند فهرس، والسلسلة الجزئية/الشريحة ⁦[a, b)⁩ مع استبعاد فهرس النهاية، والبحث ⁦(indexOf)⁩، و⁦equals⁩، و⁦compareTo⁩، والتحويل إلى أحرف كبيرة/صغيرة، والاستبدال، والتقسيم، ورموز المحارف، مع عرض النتائج جنبًا إلى جنب بالشيفرة الزائفة و⁦Python⁩ و⁦Java⁩، بما في ذلك أخطاء تجاوز النطاق. ويتقدم وضع «خوارزميات الحلقات» خطوة خطوة في عدّ محرف، وعكس سلسلة، وفحص التناظر، والبحث البسيط عن سلسلة جزئية مع جدول تتبع، ويعدّ الوضع الأخير المقارنات في البحث البسيط مقابل ⁦Boyer–Moore⁩.

الدرس: السلاسل النصية: الفهرسة، والتقطيع والسلاسل الجزئية، ودوال السلاسل، والمرور على محارف السلسلة

ماذا تعرض

السلسلة النصية متتالية غير قابلة للتغيير من المحارف، لكل محرف فهرس يبدأ من ⁦0⁩. تشمل الشريحة ⁦s[a:b]⁩ في ⁦Python⁩ والدالة ⁦s.substring(a, b)⁩ في ⁦Java⁩ الفهرس ⁦a⁩ وتستبعد الفهرس ⁦b⁩، فتعيدان ⁦b − a⁩ محارف؛ وتُطلق ⁦Java⁩ استثناءً عندما يتجاوز الفهرس النطاق، بينما يقصّ التقطيع في ⁦Python⁩ الفهارس. وتعيد دوال مثل ⁦upper⁩ و⁦replace⁩ و⁦split⁩ سلاسل جديدة. تمرّ خوارزميات الحلقات على المحارف فهرسًا بعد فهرس، ويسجّل جدول التتبع كل خطوة. أما ⁦Boyer–Moore⁩ فيبحث بمقارنة النمط من اليمين ثم يقفز إلى الأمام بعد عدم التطابق.

طريقة الاستخدام

اكتب سلسلة ⁦s⁩ (و⁦t⁩ أو ⁦r⁩ أو ⁦c⁩ عند الطلب). في «عمليات السلاسل» اختر العملية، واسحب ⁦a⁩ و⁦b⁩، وقارن النتائج في الشيفرة الزائفة و⁦Python⁩ و⁦Java⁩؛ وفعّل «إظهار رموز المحارف» لترى قيم ⁦ASCII/Unicode⁩. في «خوارزميات الحلقات» اختر الخوارزمية ولغة الشيفرة، ثم اضغط «خطوة» أو «تشغيل» وتابع السطر المميَّز وجدول التتبع. وفي «البسيط مقابل ⁦Boyer–Moore⁩» تقدّم في البحثين خطوة خطوة وقارن عدد المقارنات.

المعاملات القابلة للتغيير

  • الوضع عمليات السلاسل, خوارزميات الحلقات, البحث: البسيط مقابل ⁦Boyer–Moore⁩
  • العملية ⁦s + t⁩ (الدمج), الطول, المحرف عند الفهرس ⁦a⁩, سلسلة جزئية / شريحة ⁦[a, b)⁩, البحث عن ⁦t (find / indexOf)⁩, التساوي ⁦(equals)⁩, المقارنة ⁦(compareTo)⁩, إلى أحرف كبيرة, إلى أحرف صغيرة, استبدال ⁦t⁩ بالبديل ⁦r⁩, التقسيم عند ⁦c⁩, رمز المحرف ⁦(ord / chr)⁩
  • الخوارزمية عدّ المحرف ⁦c⁩, عكس السلسلة, فحص التناظر, البحث البسيط عن سلسلة جزئية
  • لغة الشيفرة الشيفرة الزائفة, ⁦Python, Java⁩
  • السلسلة ⁦s⁩
  • السلسلة الثانية ⁦t⁩ (النمط)
  • البديل ⁦r⁩
  • المحرف ⁦c⁩
  • الفهرس ⁦a⁩ ⁦0–28⁩
  • الفهرس ⁦b⁩ ⁦0–28⁩
  • إظهار رموز المحارف
  • السرعة ⁦0.5–10⁩ خطوة/⁦s⁩

أسئلة للاستكشاف

  1. لماذا تعيد ⁦s.substring(2, 5)⁩ ثلاثة محارف، وماذا يحدث في ⁦Java⁩ وفي ⁦Python⁩ إذا كان ⁦b⁩ أكبر من الطول؟
  2. لماذا يعطي "⁦apple⁩".⁦compareTo⁩("⁦Apple⁩") عددًا موجبًا؟
  3. لماذا يحتاج ⁦Boyer–Moore⁩ إلى مقارنات أقل من البحث البسيط عندما يكون النمط طويلًا؟