การเปรียบเทียบสัญลักษณ์ตัวแทนของ DELPHI (ฉบับที่ 5)
ผู้เขียน: หลี่ จวินยวี่
อีเมล์: [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) ด้านล่าง . การเปรียบเทียบความเร็วกับอัลกอริธึมแบบเรียกซ้ำไม่ชัดเจนในจำนวนเล็กน้อย เมื่อสตริงต้นทางมี 1 ติดต่อกัน 100 ตัว และสตริงย่อยมี 1 ติดต่อกัน 99 ตัว และสุดท้ายอักขระ 2 จะถูกเพิ่ม หลังจากการทดสอบในวงวน 1,000 ครั้ง จะเร็วกว่าอัลกอริธึมแบบเรียกซ้ำหลายวินาที และเร็วกว่า MatchesMask() 20 วินาที ฟังก์ชั่น วินาที การทดสอบหลายครั้งจริง ๆ ของฉันแสดงให้เห็นว่าทั้งสามบางครั้งเร็วที่สุด แต่ MatchesMask() ดูเหมือนว่าจะช้ากว่าเกือบตลอดเวลา และความเร็วของการเรียกซ้ำจะแตกต่างกันอย่างมาก ฟังก์ชันที่ฉันเขียนอาจมีความเร็วโดยเฉลี่ย เพียงแต่ฟังก์ชั่นที่ฉันเขียนมีไว้เพื่อการอ้างอิงเท่านั้น ฉันจะไม่รับผิดชอบต่อปัญหาใด ๆ หากเกิดขึ้น
ฟังก์ชั่น isABClikeAX(const abc,ax:widestring):boolean; file://abc เป็นสตริงต้นทาง และ ax เป็นสตริงย่อย
var
abcstart,axstart,abclength,axlength:จำนวนเต็ม;
endpartabc, endpartax, subax: สตริงกว้าง;
อุณหภูมิ, abcwww, axwww: จำนวนเต็ม;
เริ่มไฟล์://aaa
อุณหภูมิ:=0;
abcstart:=1;
แอคสตาร์ท:=1;
อ๊ากกก:=1;
abcwww:=1;
ความยาว abc:=ความยาว(abc);
ความยาวแกน:=ความยาว(ขวาน);
isabclikeax:=จริง;
ในขณะที่ axstart<=axlength ทำ//เมื่อความยาวสตริงต้นทางมากกว่าหรือเท่ากับสตริงย่อย
เริ่ม//bbb
ถ้า abcstart> abclength แล้ว
เริ่ม
ถ้า (ax[axlength]='*') และ (axlength=axstart) ดังนั้น isabclikeax:=true
else isabclikeax:=false;//เมื่อสตริงย่อยยาวกว่าสตริงต้นทาง
หยุดพัก;
จบ;
ถ้า ax[axstart]='?' แล้ว
เริ่ม
Inc(axstart);
Inc(abcstart);
ดำเนินการต่อ;
จบ;
ถ้า ax[axstart]='*' แล้ว
เริ่ม
Inc(axstart);
อุณหภูมิ:=1;
axwww:=axstart;
abcwww:=abcstart;
ดำเนินการต่อ;
จบ;
ถ้าไม่((ax[axstart]='?') หรือ (ax[axstart]='*') ) แล้ว
เริ่ม//ccc
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;
ส่วนท้าย:=copy(abc,abcstart,abclength-abcstart+1);
ถ้า ((pos(subax,endpartabc)<>0) และ (temp=1 )) หรือ ((pos(subax,endpartabc)=1) และ (temp=0)) แล้ว
เริ่ม//ddd
ถ้า temp=1 แล้ว temp:=0;
abcstart:=abcstart+(pos(subax,endpartabc)+ความยาว(subax)-1) ;
จบ//ddd
อย่างอื่น//ddd
เริ่ม//ddd
ถ้า (temp=0) และ (axwww>1) แล้ว
เริ่ม
axstart:=axwww;
abcwww:=abcwww+1;
abcstart:=abcwww;
อุณหภูมิ:=1;
ดำเนินการต่อ;
จบ;
isabclikeax:=เท็จ;
หยุดพัก;
จบ;//ddd
จบ;//ccc
จบ;//bbb
if (result) และ (abcstart<=abclength) และ (ax[axlength]<>'*') ดังนั้น isabclikeax:=false;//เมื่อสตริงต้นทางยาวกว่าสตริงย่อย
จบ;//อร๊าย
ฟังก์ชัน IsLike(abc,ax:string):boolean; file://case-sensitive function
เริ่ม
islike:=isABClikeAX(abc,ขวาน);
จบ;
ฟังก์ชัน WideCard (abc, ขวาน: สตริง): บูลีน; ไฟล์: // ฟังก์ชันไม่คำนึงถึงขนาดตัวพิมพ์
เริ่ม
abc:=ตัวพิมพ์ใหญ่(abc);
ขวาน:=ตัวพิมพ์ใหญ่(ขวาน);
ไวด์การ์ด:=isABClikeAX(abc,ขวาน);
จบ;
โปรดใส่ใจกับ USES MATH เนื่องจากมีการใช้ MIN() คุณจึงสามารถใช้คำสั่ง IF เพื่อแทนที่ MIN() ได้ แต่ก็ยังไม่ชัดเจนเพียงพอ
ขอบคุณชาวเน็ตบางส่วนที่ให้ข้อมูลเชิงลึกที่ถูกต้อง ช่วยให้ผมแก้ไขได้ถูกต้องครับ