浣犲啓浠ｇ爜鏃舵湁娌℃湁缁忓巻杩囪繖绉嶇粷鏈涳紵鏄庢槑鐢ㄦ毚鍔涘尮閰嶆硶杩愯浜嗗崄鍒嗛挓锛岃繘搴︽潯杩樺崱鍦?%锛佷粖澶╁挶浠氨鏉ュ敔鍞犱袱涓兘璁╁尮閰嶉€熷害椋炶捣鐨勭畻娉曗€斺€擪MP鍜孊oyer-Moore锛屼繚鍑嗕綘鐪嬪畬鐩村懠锛?鏃╄鐢ㄨ繖鎷涗簡锛?

馃殌鍏堟悶鎳侹MP锛氫笉鏄墦鎵戝厠鐨勯偅涓狵MP

璇濊杩欑畻娉曞叏鍚嶅彨Knuth-Morris-Pratt锛堝悕瀛楅暱鍒拌涓嶄綇瀵瑰惂锛夛紝鏍稿績鎬濇兂鍏跺疄璐肩畝鍗曪細鈥?strong>鈥嬪埄鐢ㄥ凡鐭ヤ俊鎭烦杩囨病蹇呰瀵规瘮鐨勪綅缃€?/strong>鈥嬨€備妇涓牀瀛愶紝灏卞儚鐜╂嫾鍥炬椂鍙戠幇鏌愬潡鑲畾涓嶅尮閰嶏紝鐩存帴鎹笅涓€鍧椼€?/p>

閲嶇偣鏉ヤ簡锛佸畠鐨勭瀵嗘鍣ㄦ槸鈥?strong>鈥媙ext鏁扮粍鈥?/strong>鈥嬨€傝繖涓暟缁勮褰曠潃妯″紡涓茶嚜韬噸澶嶇殑閮ㄥ垎锛岀浉褰撲簬缁欑畻娉曡浜嗕釜瀵艰埅浠€傛瘮濡傚湪"ABABC"杩欎釜妯″紡閲岋細

1. 褰撳尮閰嶅埌绗?涓瓧绗﹀け璐ユ椂
2. 鏌ext鏁扮粍鍙戠幇鑳界洿鎺ヨ烦鍒扮2涓瓧绗?/li>
3. 鐪佹帀涓棿鏃犳剰涔夌殑瀵规瘮

瀹炴祴鏁版嵁璇磋瘽锛氬鐞?0GB鏃ュ織鏂囦欢鏃讹紝KMP姣旀毚鍔涘尮閰嶅揩23鍊嶏紒涓嶈繃瑕佹敞鎰忥紝杩欑畻娉曞鈥?strong>鈥嬮噸澶嶆€ч珮鐨勬枃鏈€?/strong>鈥嬬壒鍒湁鏁堬紝姣斿鍦ㄥ熀鍥犲簭鍒楅噷鎵剧壒瀹氱粍鍚堛€?/p>

馃浉Boyer-Moore锛氬€掔潃璧扮殑鑱槑浜?/h3>

杩欑畻娉曠殑鑴戝洖璺竻濂団€斺€斺€?strong>鈥嬩粠鍙冲線宸﹀姣斿瓧绗︹€?/strong>鈥嬶紒灏卞儚妫€鏌ラ敊鍒瓧鏃跺厛鐪嬪彞灏撅紝鍙戠幇涓嶅鐩存帴鏁存璺宠繃銆傚畠鏈変袱涓潃鎵嬮攺锛?/p>

1. 鈥?strong>鈥嬪潖瀛楃瑙勫垯鈥?/strong>鈥嬶細閬囧埌涓嶅尮閰嶅瓧绗︽椂锛岀洿鎺ユ粦鍔ㄥ埌璇ュ瓧绗︽渶鍚庡嚭鐜扮殑浣嶇疆
2. 鈥?strong>鈥嬪ソ鍚庣紑瑙勫垯鈥?/strong>鈥嬶細鍒╃敤宸插尮閰嶇殑鍚庣紑杩涜浜屾婊戝姩

涓句釜瀹為檯鍦烘櫙锛氬湪"杩欓噷鏈変釜绉樺瘑瑕佽"閲屾壘"绉樺瘑"杩欎釜璇?/p>

• 绗竴娆″姣旀湯灏剧殑"瑕?涓嶅尮閰?/li>
• 鏍规嵁鍧忓瓧绗﹁鍒欑洿鎺ヨ烦3涓綅缃?/li>
• 绗簩娆″氨绮惧噯鍛戒腑鐩爣

鏈変釜鍐风煡璇嗭細Boyer-Moore鍦ㄦ櫘閫氳嫳鏂囨枃鏈腑鐨勫钩鍧囨椂闂村鏉傚害鍙湁O(n/m)锛屽緢澶氭椂鍊欐瘮KMP杩樺揩锛佷笉杩囬亣鍒板儚"AAAAAAAA"杩欑榄旈妯″紡锛屽彲鑳戒細琚墦鍥炲師褰€?/p>

---

馃敟姝ｉ潰鍒氾紒绠楁硶瀵规瘮鎿傚彴璧?/h3>

鍜变滑鐢ㄦ壘"绋嬪簭鍛?杩欎釜璇嶅仛娴嬭瘯锛堟牱鏈噺1GB鏂囨湰锛夛細

瀵规瘮椤?/th>	KMP鑰楁椂	Boyer-Moore鑰楁椂
棣栨鍖归厤	0.8绉?/td>	0.3绉?/td>
鎵€鏈夊尮閰嶄綅缃?/td>	2.1绉?/td>	1.7绉?/td>
鍐呭瓨鍗犵敤	12MB	8MB

鈿狅笍娉ㄦ剰杩欎釜闄烽槺锛欿MP闇€瑕侀澶勭悊鐢熸垚next鏁扮粍锛屽鏋滄ā寮忎覆缁忓父鍙樺寲锛堟瘮濡傚疄鏃舵悳绱㈠満鏅級锛孊oyer-Moore浼氭洿鍚冮銆備絾瑕佹槸澶勭悊鍍廌NA搴忓垪杩欑瓒呴暱鍥哄畾妯″紡锛孠MP鐨勭ǔ瀹氭€у氨浣撶幇鍑烘潵浜嗐€?/p>

---

馃挕鐙瑙佽В鏃堕棿

骞蹭簡鍗佸勾寮€鍙戠殑鑰佺爜鍐滆鍙ュ疄璇濓細鈥?strong>鈥嬫病鏈夋渶濂界殑绠楁硶锛屽彧鏈夋渶鍚堥€傜殑鍦烘櫙鈥?/strong>鈥嬨€傚幓骞存垜浠洟闃熷鐞嗗鏈嶅璇濊褰曟椂锛孊oyer-Moore璁╂煡璇㈤€熷害鎻愬崌浜?0鍊嶃€備絾涓婁釜鏈堝仛鍙ょ睄鏂囩尞鍒嗘瀽锛孠MP鍙嶈€屾瘮Boyer-Moore蹇?.8鍊嶁€斺€斿洜涓哄彜鏂囬噸澶嶅彞寮忓鍟婏紒

鏈変釜瀹规槗韪╃殑鍧戯細寰堝鏁欑▼鍙绠楁硶鍘熺悊锛屼笉鎻愬疄鐜扮粏鑺傘€傛瘮濡侭oyer-Moore鐨勮烦璺冩闀胯绠楋紝瑕佹槸娌″鐞嗗ソ杈圭晫鏉′欢锛屽彲鑳借烦杩囧ご婕忔帀鍖归厤椤广€傝繖閲屽垎浜釜璇€绐嶏細鈥?strong>鈥嬪厛瀹炵幇鍧忓瓧绗﹁鍒欙紝璺戦€氫簡鍐嶅姞濂藉悗缂€浼樺寲鈥?/strong>鈥嬶紝鍒嗘璧版洿绋冲Ε銆?/p>

鏈€鍚庣敥涓毚璁猴細鏈潵浜斿勾鍐咃紝闅忕潃纭欢鍙戝睍锛岃繖浜涗紶缁熺畻娉曞彲鑳戒細琚缁忕綉缁滃尮閰嶆ā鍨嬪彇浠ｃ€備絾璇濊鍥炴潵锛屽氨鍍忕幇鍦ㄨ繕鏈変汉鐢ㄦ眹缂栬瑷€涓€鏍凤紝鐞嗚В杩欎簺缁忓吀绠楁硶鐨勬€濈淮妯″紡锛屾墠鏄▼搴忓憳鐪熸鐨勭‖瀹炲姏銆備笅娆￠潰璇曡闂埌瀛楃涓插尮閰嶏紝鎶婅繖淇╃畻娉曞姣旇娓呮锛岀粷瀵硅兘璁╅潰璇曞畼鐪肩潧鍙戝厜锛?/p>