مقارنة DELPHI's Wildcard (الإصدار الخامس)

مقارنة DELPHI's Wildcard (الإصدار الخامس)

المؤلف: لي جونيو

البريد الإلكتروني: [email protected] 2003.1.5

اعتقدت أنه لا توجد وظيفة جاهزة لأحرف البدل في DELPHI، ولكن بعد ذلك وجدت MatchesMask(). قبل أن أجد هذه الوظيفة، كنت أقوم بإنشاء وظيفة مخصصة لتحقيق هذه الوظيفة عندما كنت في حالة حرة وما زلت في حالة مزاجية.

خوارزمية البرنامج أكثر تعقيدًا. قم أولاً بإضافة "؟" في نهاية السلسلة الفرعية. *'، ثم اقرأ السلسلة الفرعية، وابحث عن الأحرف بين أحرف البدل في السلسلة الفرعية، أي السلسلة الفرعية في السلسلة الفرعية، ثم ابحث في السلسلة المصدر لمعرفة ما إذا كانت تحتوي على السلسلة الفرعية في السلسلة الفرعية لا يزال تنفيذه مكلفًا، حيث العديد من التقلبات والمنعطفات. تنفذ هذه الوظيفة الوظائف التالية:

1. قد يكون أسرع من الخوارزمية العودية وMatchesMask() في معظم الحالات؛

2. تم تنفيذ المقارنة الصحيحة بين العلامات النجمية وعلامات الاستفهام في جميع الحالات؛ // قد لا يزال هذا بحاجة إلى وقت للتحقق

3. دعم اللغة الصينية; // يجب أن تكون العلامات النجمية وعلامات الاستفهام باللغة الإنجليزية حتى تكون صالحة

4. يدعم التحديد الحساس لحالة الأحرف.

لاحظ أن هناك فرقًا بين إضافة العلامات النجمية في بداية السلسلة الفرعية ونهايتها. قد تكون هذه الخوارزمية مشابهة للوظيفة التي يتم تنفيذها باستخدام الخوارزمية العودية على المكدس، ولكنها في الواقع مختلفة إلى حد ما، فقد أدخلت بعض التحسينات على العودية، وقد تكون أسرع من العملية العودية في معظم الحالات ؟ بالتأكيد. على الأقل يوجد هذا التقدير: عندما يتم استخدام مقارنة أحرف البدل فقط للعثور على سلاسل فرعية، مثل السلسلة المصدر هي "1111111111" والسلسلة الفرعية هي "*11111112*"، فإن التعقيد الزمني لاستخدام الخوارزمية العودية هو O(N*M) )، ولكنني كتبت سيتم بعد ذلك تبسيط هذه الوظيفة إلى التعقيد الزمني لاستدعاء وظيفة POS() تقريبًا عدة مرات ربما يمكن تخيل POS() في DELPHI على أنها "خوارزمية Knut-Morris-Pratt (KMP)" O(N+M) أدناه. . مقارنة السرعة مع الخوارزمية العودية ليست واضحة لعدد قليل من المرات. عندما تحتوي السلسلة المصدر على 100 رقم 1 متتالي والسلسلة الفرعية تحتوي على 99 رقم 1 متتالي وأخيراً تتم إضافة الحرف 2، بعد الاختبار في حلقة 1000 مرة، يكون ذلك أسرع بعدة ثوانٍ من الخوارزمية العودية وأسرع بـ 20 ثانية من MatchesMask() وظيفة. تُظهر اختباراتي المتعددة الفعلية أن الثلاثة جميعًا هم الأسرع في بعض الأحيان، ولكن يبدو أن MatchesMask() أبطأ في معظم الأوقات، وقد تختلف سرعة التكرار بشكل كبير. إن الوظائف التي كتبتها هي للإشارة فقط ولن أكون مسؤولاً عن أي مشاكل في حالة حدوثها.

الوظيفة هيABClikeAX(const abc,ax:widestring):boolean file://abc هي السلسلة المصدر والفأس هي السلسلة الفرعية

فار

abcstart,axstart,abclength,axlength:integer;

endpartabc,endpartax,subax:widestring;

درجة الحرارة، ABCwww، axwww:integer؛

بداية الملف:://aaa

درجة الحرارة:=0;

abcstart:=1;

axstart:=1;

axwww:=1;

abcwww:=1;

abclength:=length(abc);

طول المحور:=طول(فأس);

isabclikeax:=true;

while axstart<=axlength do// عندما يكون طول السلسلة المصدر أكبر من أو يساوي السلسلة الفرعية

تبدأ //بب

إذا abcstart> abclength ثم

يبدأ

إذا (ax[axlength]='*') و (axlength=axstart) ثم isabclikeax:=true

else isabclikeax:=false;// عندما تكون السلسلة الفرعية أطول من السلسلة المصدر

استراحة؛

نهاية؛

إذا كان الفأس [axstart] = '؟'

يبدأ

المؤتمر الوطني العراقي(axstart);

المؤتمر الوطني العراقي(abcstart);

يكمل؛

نهاية؛

إذا كان ax[axstart]='*' إذن

يبدأ

المؤتمر الوطني العراقي(axstart);

درجة الحرارة:=1;

axwww:=axstart;

abcwww:=abcstart;

يكمل؛

نهاية؛

إذا لم يكن ((ax[axstart]='?') أو (ax[axstart]='*')) ) إذن

تبدأ // سي سي سي

endpartax:=copy(ax,axstart,axlength-axstart+1)+'?*';

subax:=copy(endpartax,1,min(pos('?',endpartax),pos('*',endpartax))-1);

axstart:=axstart+min(pos('?',endpartax),pos('*',endpartax))-1;

endpartabc:=copy(abc,abcstart,abclength-abcstart+1);

إذا ((pos(subax,endpartabc)<>0) و (temp=1 )) أو ((pos(subax,endpartabc)=1) و (temp=0)) ثم

تبدأ // يدد

إذا درجة الحرارة = 1 ثم درجة الحرارة: = 0؛

abcstart:=abcstart+(pos(subax,endpartabc)+length(subax)-1) ;

النهاية //ddd

آخر //ddd

تبدأ // يدد

إذا (درجة الحرارة = 0) و (axwww>1) ثم

يبدأ

axstart:=axwww;

abcwww:=abcwww+1;

abcstart:=abcwww;

درجة الحرارة:=1;

يكمل؛

نهاية؛

isabclikeax:=false;

استراحة؛

النهاية؛//ددد

النهاية;//ccc

النهاية؛//بب

إذا (نتيجة) و (abcstart<=abclength) و (ax[axlength]<>'*') ثم isabclikeax:=false;// عندما تكون السلسلة المصدر أطول من السلسلة الفرعية

النهاية؛//aaa

FUNCTION IsLike(abc,ax:string):boolean; file://sensitive function

يبدأ

islike:=isABClikeAX(abc,ax);

نهاية؛

FUNCTION WideCard(abc,ax:string):boolean; file://وظيفة غير حساسة لحالة الأحرف

يبدأ

اي بي سي:=الأحرف الكبيرة(اي بي سي);

الفأس:=الأحرف الكبيرة(الفأس);

Widecard:=isABClikeAX(abc,ax);

نهاية؛

انتبه إلى USES MATH، نظرًا لاستخدام MIN()، يمكنك أيضًا استخدام عبارة IF لاستبدال MIN()، ولكنها ليست واضحة بدرجة كافية.

شكرًا لبعض مستخدمي الإنترنت على إعطائي بعض الأفكار الصحيحة، مما ساعدني في إجراء المراجعة في الاتجاه الصحيح.