56. خوارزميات مطابقة السلاسل النصية: مقدمة للمنهج الساذج (Naive Approach)

مطابقة السلاسل النصية هي مشكلة العثور على تكرارات لسلسلة 'نمط' P داخل سلسلة 'نص' أكبر T.

الخوارزمية الساذجة (The Naive Algorithm)

النهج الأبسط هو طريقة القوة الغاشمة (brute-force)، حيث نتحقق من كل موضع ممكن في النص حيث قد يبدأ النمط.

البدء من الفهرس i = 0 في النص T.
مقارنة النمط P (بطول M) حرفاً بحرف مع السلسلة الفرعية لـ T التي تبدأ عند i.
إذا تطابقت جميع الأحرف، يتم العثور على تطابق.
إذا حدث عدم تطابق، قم بإزاحة النمط بموضع واحد (زيادة i) وابدأ المقارنة مرة أخرى.

إذا كان طول النص N وطول النمط M:

الوقت في أسوأ حالة: O(N * M).
- يحدث هذا إذا كان النمط والنص متطابقين تقريباً في كل موضع (على سبيل المثال، Text = 'AAAAAB'، Pattern = 'AAAB'). تجري الخوارزمية ما يقرب من M مقارنة N مرة.

لإجراء مطابقة عملية وأسرع للسلاسل، من الضروري استخدام خوارزميات أكثر تقدماً مثل KMP أو Rabin-Karp.