ในบรรดาอัลกอริธึมการค้นหาการจับคู่สตริง สองอัลกอริธึมที่มีชื่อเสียงที่สุดคืออัลกอริธึม KMP (Knuth-Morris-Pratt) และอัลกอริธึม BM (Boyer-Moore) อัลกอริธึมทั้งสองมีเวลาค้นหาเชิงเส้นในกรณีที่แย่ที่สุด อย่างไรก็ตาม ในทางปฏิบัติ อัลกอริธึม KMP ไม่ได้เร็วกว่าฟังก์ชันไลบรารี C ที่ง่ายที่สุดมากนัก strstr() ในขณะที่อัลกอริธึม BM มักจะเร็วกว่าอัลกอริธึม KMP ถึง 3-5 เท่า (ไม่ได้ฝึกฝนเป็นการส่วนตัว) อย่างไรก็ตาม อัลกอริธึม BM ยังไม่ใช่อัลกอริธึมที่เร็วที่สุด นี่คืออัลกอริธึมการค้นหา อัลกอริธึม Sunday ซึ่งเร็วกว่าอัลกอริธึม BM
แนวคิดของอัลกอริทึม Sunday นั้นคล้ายคลึงกับแนวคิดเรื่องอักขระที่ไม่ดีในอัลกอริทึม BM มาก ข้อแตกต่างเพียงอย่างเดียวคือ หลังจากที่อัลกอริธึม Sunday ไม่สามารถจับคู่ได้ อักขระจะใช้เวลาหนึ่งตำแหน่งหลังส่วนปัจจุบันของสตริงเป้าหมายที่สอดคล้องกับสตริง Pattern เพื่อทำการจับคู่อักขระที่ไม่ถูกต้อง เมื่อพบว่าการจับคู่ล้มเหลว ระบบจะตัดสินว่ามีอักขระที่ออฟเซ็ตปัจจุบัน + ความยาวสตริงรูปแบบ + 1 (ซึ่งถือเป็นตำแหน่ง K) ในสตริงพาเรนต์มีอยู่ในสตริงรูปแบบหรือไม่ ถ้ามี ให้จัดตำแหน่งด้วยอักขระในสตริง Pattern จากนั้นจับคู่ตั้งแต่ต้น หากไม่มี ให้ย้ายสตริง Pattern ไปข้างหลัง จัดตำแหน่งให้ตรงกับอักขระที่ k+1 ของสตริงพาเรนต์ จากนั้น จับคู่. ทำซ้ำการดำเนินการข้างต้นจนกว่าจะพบ หรือพบสตริงหลัก ฉันเขียนตัวอย่างเล็กๆ น้อยๆ เพื่อใช้อัลกอริทึมต่อไปนี้
ในโค้ดจะมีการใช้อัลกอริธึมการจับคู่สตริงสองแบบ วิธีหนึ่งคือวิธี Sunday และอีกวิธีหนึ่งคือวิธีธรรมดาในการย้ายทีละบิต การเปรียบเทียบประสิทธิภาพของทั้งสองจะแสดงในฟังก์ชันหลัก ทั้งสองแบบที่ระดับนาโนวินาที . ขั้นตอนโดยละเอียดของอัลกอริทึมได้รับการเพิ่มพร้อมความคิดเห็นที่เกี่ยวข้องในโค้ด ส่วนอัลกอริธึม BM เราจะเปรียบเทียบและวิเคราะห์ร่วมกันในครั้งต่อไปเมื่อว่างเปล่า
คัดลอกรหัสรหัสดังต่อไปนี้:
นำเข้า java.util.HashMap;
นำเข้า java.util.LinkedList;
นำเข้า java.util.List;
นำเข้า java.util.Map;
-
* @ผู้เขียน สกอตต์
* @วันที่ 28 ธันวาคม 2556
* @คำอธิบาย
-
SundySearch คลาสสาธารณะ {
ข้อความสตริง = null;
รูปแบบสตริง = null;
int currentPos = 0;
-
* รายการตำแหน่งอักขระตัวแรกของสตริงย่อยที่ตรงกัน
-
รายการ<จำนวนเต็ม>matchedPosList = ใหม่ LinkedList<จำนวนเต็ม>();
-
* แผนผังของอักขระที่ตรงกัน บันทึกอักขระที่อยู่ในสตริงที่ตรงกัน และการกระจัดครั้งสุดท้ายของแต่ละอักขระ
-
แผนที่ <ตัวละคร, จำนวนเต็ม> แผนที่ = ใหม่ HashMap<ตัวละคร, จำนวนเต็ม>();
SundySearch สาธารณะ (ข้อความสตริง รูปแบบสตริง) {
this.text = ข้อความ;
this.pattern = รูปแบบ;
นี้.initMap();
-
-
* เมื่อจับคู่วันอาทิตย์ จะใช้จัดเก็บตำแหน่งสุดท้ายที่ปรากฏของตัวละครแต่ละตัวในรูปแบบ Pattern เรียงจากซ้ายไปขวา
-
โมฆะส่วนตัว initMap() {
สำหรับ (int i = 0; i < pattern.length(); i++) {
this.map.put(รูปแบบ.charAt(i), i);
-
-
-
* การจับคู่สตริงแบบเรียกซ้ำปกติ หากการจับคู่ล้มเหลว ให้เลื่อนไปหนึ่งตำแหน่ง
-
รายการสาธารณะ <จำนวนเต็ม> NormalMatch() {
//จับคู่ไม่สำเร็จ ลงต่อ
ถ้า (!matchFromSpecialPos(currentPos)) {
ตำแหน่งปัจจุบัน += 1;
ถ้า ((text.length() - currentPos) < pattern.length()) {
ส่งคืนการจับคู่ PosList;
-
การจับคู่ปกติ();
} อื่น {
//จับคู่สำเร็จ บันทึกตำแหน่ง
matchedPosList.add(currentPos);
ตำแหน่งปัจจุบัน += 1;
การจับคู่ปกติ();
-
ส่งคืนการจับคู่ PosList;
-
-
* การจับคู่วันอาทิตย์ สมมติว่าตำแหน่งของอักขระ K ในข้อความคือ: ออฟเซ็ตปัจจุบัน + ความยาวสตริงรูปแบบ + 1
-
รายการสาธารณะ <จำนวนเต็ม> SundayMatch () {
// หากไม่มีการแข่งขันใดสำเร็จ
ถ้า (!matchFromSpecialPos(currentPos)) {
// หากอักขระ K ในข้อความไม่ปรากฏในสตริงรูปแบบ ให้ข้ามความยาวสตริงรูปแบบทั้งหมด
ถ้า ((currentPos + pattern.length() + 1) < text.length()
&& !map.containsKey(text.charAt(currentPos + pattern.length() + 1))) {
currentPos += pattern.length();
}อื่น {
// หากอักขระ K ในข้อความปรากฏในสตริงรูปแบบ ให้จัดตำแหน่งของอักขระ K ในข้อความให้ตรงกับตำแหน่งของอักขระ K ตัวสุดท้ายในสตริงรูปแบบ
ถ้า ((currentPos + pattern.length() + 1) > text.length()) {
ตำแหน่งปัจจุบัน += 1;
} อื่น {
currentPos += pattern.length() - (จำนวนเต็ม) map.get(text.charAt(currentPos + pattern.length()));
-
-
// เมื่อการแข่งขันเสร็จสิ้น ให้คืนค่าการกระจัดเริ่มต้นของการแข่งขันที่สำเร็จทั้งหมด
ถ้า ((text.length() - currentPos) < pattern.length()) {
ส่งคืนการจับคู่ PosList;
-
ซันเดย์แมตช์();
}อื่น {
//หากแมตช์สำเร็จ ให้เลื่อนไปหนึ่งบิตแล้วแมตช์ใหม่อีกครั้ง
matchedPosList.add(currentPos);
ตำแหน่งปัจจุบัน += 1;
ซันเดย์แมตช์();
-
ส่งคืนการจับคู่ PosList;
-
-
* ตรวจสอบว่าสตริงย่อยที่เริ่มต้นจากออฟเซ็ตที่ระบุของข้อความตรงกับรูปแบบหรือไม่
-
การแข่งขันบูลีนสาธารณะFromSpecialPos (int pos) {
ถ้า ((text.length()-pos) < pattern.length()) {
กลับเท็จ;
-
สำหรับ (int i = 0; i < pattern.length(); i++) {
ถ้า (text.charAt(pos + i) == pattern.charAt(i)) {
ถ้า (i == (รูปแบบความยาว()-1)) {
กลับเป็นจริง;
-
ดำเนินการต่อ;
} อื่น {
หยุดพัก;
-
-
กลับเท็จ;
-
โมฆะคงที่สาธารณะ main (String [] args) {
SundySearch sundySearch = ใหม่ SundySearch("สวัสดี อา Adolf adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwersdf2666sdflsdfk", "adf");
เริ่มต้นนาน = System.nanoTime();
System.out.println("NormalMatch:" + sundySearch.normalMatch());
System.out.println("NormalMatch:" + (System.nanoTime() - เริ่ม));
เริ่มต้น = System.nanoTime();
System.out.println("SundayMatch:" + sundySearch.sundayMatch());
System.out.println("SundayMatch:" + (System.nanoTime() - เริ่ม));
-
-