البحث عن سلسلة فرعية في C++: من السذاجة إلى الأداء

مقدمة: لماذا "مجرد find()" ليس دائمًا الإجابة

تخيل موقفًا: أنت تكتب محلل سجلات يعالج ملايين الأسطر في الثانية، أو محرك بحث نصي. أول ما يتبادر إلى الذهن هو استدعاء std::string::find(). "هل يعمل؟ يعمل. ماذا تحتاج أيضًا؟" - يفكر 90% من المبرمجين. وهم على حق... حتى تأتي اللحظة التي تحدد فيها 10 مللي ثانية مصير التطبيق بأكمله.

سؤال "Check if a string contains a string in C++" على Stack Overflow حصد مئات الآلاف من المشاهدات. وهذا ليس من قبيل الصدفة. فالمهمة التي تبدو تافهة تخفي العديد من المزالق: من اختيار خوارزمية البحث إلى الاستخدام الصحيح لإمكانيات C++17 و C++20 الحديثة.

في هذه المقالة، لن نعرض فقط كيفية التحقق مما إذا كانت السلسلة تحتوي على سلسلة فرعية. سنحلل 7 طرق للقيام بذلك، ونقارن أداءها على بيانات حقيقية، ونقدم توصيات واضحة لسيناريوهات مختلفة. هيا بنا!

الكلاسيكية: std::string::find()

لنبدأ بالأساسيات التي يعرفها الجميع. الطريقة find() تُرجع موضع أول ظهور للسلسلة الفرعية أو القيمة الخاصة std::string::npos إذا لم يتم العثور على شيء.

#include <iostream>\n#include <string>\n\nint main() {\n    std::string haystack = "Hello, C++ developer!";\n    std::string needle = "C++";\n    \n    if (haystack.find(needle) != std::string::npos) {\n        std::cout << "تم العثور على السلسلة الفرعية!" << std::endl;\n    }\n    \n    // البحث مع تحديد موضع البداية\n    size_t pos = haystack.find("C++", 5); // نبدأ من الحرف الخامس\n    return 0;\n}

الإيجابيات: البساطة، سهولة القراءة، مدمج في STL.
\nالسلبيات: يستخدم خوارزمية بحث ساذجة (O(n*m) في أسوأ الحالات). للسلاسل القصيرة - مثالي، للطويلة - قد يبطئ.

متى يكون find() سيئًا؟

إذا كنت تبحث عن سلسلة فرعية في سلسلة طولها 10⁵+ حرفًا، وكانت السلسلة الفرعية طويلة ومتكررة (مثل "aaaaaab" في "aaaaaaaaaaaaaaaaaaaaab")، تبدأ الخوارزمية الساذجة في التدهور. في مثل هذه الحالات، يمكن أن يعمل find() أبطأ بمقدار 10-100 مرة من البدائل المحسّنة.

string_view: الخفة والسرعة

مع ظهور C++17، أصبح لدينا std::string_view - تمثيل غير مالك للسلسلة. إنه مثالي للوظائف التي تقرأ البيانات فقط دون نسخها.

#include <iostream>\n#include <string_view>\n\nbool contains(std::string_view haystack, std::string_view needle) {\n    return haystack.find(needle) != std::string_view::npos;\n}\n\nint main() {\n    std::string_view text = "التحسين في C++ هو فن";\n    std::string_view pattern = "فن";\n    \n    if (contains(text, pattern)) {\n        std::cout << "تم العثور عليه!" << std::endl;\n    }\n    return 0;\n}

لماذا هذا أسرع؟ عند تمرير std::string إلى دالة، يحدث نسخ (إذا لم يتم تمريره بالمرجع). string_view ينسخ فقط المؤشر والطول - لا توجد تخصيصات ذاكرة. للاستدعاءات المتكررة للتحقق من الوجود، يعطي هذا زيادة في الأداء تصل إلى 30-40%.

الترقية الخوارزمية: Boyer-Moore و KMP

إذا كنت تعمل مع بيانات كبيرة حقًا، فقد حان الوقت لتذكر الخوارزميات الكلاسيكية للبحث عن السلسلة الفرعية. في C++17 ظهرت خوارزميات البحث من STL:

\n
• std::boyer_moore_searcher - واحدة من أسرع الخوارزميات للأنماط الطويلة
\n
• std::boyer_moore_horspool_searcher - نسخة مبسطة، أسرع على الأنماط القصيرة
\n
• std::default_searcher - غلاف للبحث الساذج
\n

#include <iostream>\n#include <string>\n#include <algorithm>\n#include <functional>\n\nint main() {\n    std::string text = "خوارزميات البحث في C++ يمكن أن تكون سريعة جدًا";\n