📄 字串核對.mht
字号:
From: <由 Microsoft Internet Explorer 5 保存>
Subject: =?gb2312?B?19a0rrrLjKY=?=
Date: Wed, 13 Sep 2006 01:11:34 +0800
MIME-Version: 1.0
Content-Type: multipart/related;
boundary="----=_NextPart_000_0056_01C6D6D1.8DC3B4C0";
type="text/html"
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1807
This is a multi-part message in MIME format.
------=_NextPart_000_0056_01C6D6D1.8DC3B4C0
Content-Type: text/html;
charset="big5"
Content-Transfer-Encoding: quoted-printable
Content-Location: http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip/MatchString.htm
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>=A6r=A6=EA=AE=D6=B9=EF</TITLE>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Dbig5"><LINK=20
href=3D"http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip=
/css/stdlayout.css"=20
type=3Dtext/css rel=3Dstylesheet><LINK=20
href=3D"http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip=
/css/print.css"=20
type=3Dtext/css rel=3Dstylesheet>
<META content=3D"MSHTML 6.00.2800.1561" name=3DGENERATOR></HEAD>
<BODY>
<H3><A=20
href=3D"http://caterpillar.onlyfun.net/Gossip/index.html">http://caterpil=
lar.onlyfun.net/Gossip/index.html</A></H3>
<H1><A=20
href=3D"http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip=
/AlgorithmGossip.htm">Algorithm=20
Gossip: =A6r=A6=EA=AE=D6=B9=EF</A></H1>
<H2> =BB=A1=A9=FA</H2>=A4=B5=A4=E9=AA=BA=A4@=A8=C7=B0=AA=B6=A5=B5{=A6=
=A1=BBy=A8=A5=B9=EF=A9=F3=A6r=A6=EA=AA=BA=B3B=B2z=A4=E4=B4=A9=B6V=A8=D3=B6=
V=B1j=A4j=A1]=A8=D2=A6pJava=A1BPerl=B5=A5=A1^=A1A=A4=A3=B9L=A6r=A6=EA=B7j=
=B4M=A5=BB=A8=AD=A4=B4=ACO=AD=D3=AD=C8=B1o=B1=B4=B0Q=AA=BA=BD=D2=C3D=A1A=A6=
b=B3o=C3=E4=A5HBoyer-=20
Moore=AAk=A8=D3=BB=A1=A9=FA=A6p=A6=F3=B6i=A6=E6=A6r=A6=EA=BB=A1=A9=FA=A1A=
=B3o=AD=D3=A4=E8=AAk=A7=D6=A5B=AD=EC=B2z=C2=B2=BC=E4=A9=F6=C0=B4=A1C<BR>
<H2>=B8=D1=AAk</H2>=A6r=A6=EA=B7j=B4M=A5=BB=A8=AD=A4=A3=C3=F8=A1A=A8=CF=A5=
=CE=BC=C9=A4O=AAk=A4]=A5i=A5H=A8D=B8=D1=A1A=A6=FD=A6p=A6=F3=A7=D6=B3t=B7j=
=B4M=A6r=A6=EA=B4N=A4=A3=C2=B2=B3=E6=A4F=A1A=B6=C7=B2=CE=AA=BA=A6r=A6=EA=B7=
j=B4M=ACO=B1q=C3=F6=C1=E4=A6r=BBP=A6r=A6=EA=AA=BA=B6}=C0Y=B6}=A9l=A4=F1=B9=
=EF=A1A=A8=D2=A6p <A=20
href=3D"http://www.ics.uci.edu/~eppstein/161/960227.html">Knuth-Morris-Pr=
att=20
=BAt=BA=E2=AAk</A>=20
=A6r=A6=EA=B7j=B4M=A1A=B3o=AD=D3=A4=E8=AAk=A4]=A4=A3=BF=F9=A1A=A4=A3=B9L=AD=
n=AA=E1=AE=C9=B6=A1=A6b=A4=BD=A6=A1=ADp=BA=E2=A4W=A1FBoyer-Moore=A6r=A6=EA=
=AE=D6=B9=EF=A7=EF=A5=D1=C3=F6=C1=E4=A6r=AA=BA=AB=E1=AD=B1=B6}=A9l=AE=D6=B9=
=EF=A6r=A6=EA=A1A=A8=C3=BBs=A7@=ABe=B6i=AA=ED=A1A=A6p=AAG=A4=F1=B9=EF=A4=A3=
=B2=C5=A6X=ABh=A8=CC=ABe=B6i=AA=ED=A4=A4=AA=BA=AD=C8=ABe=B6i=A6=DC=A4U=A4=
@=AD=D3=AE=D6=B9=EF=B3B=A1A=B0=B2=B3]=ACOp=A6n=A4F=A1A=B5M=AB=E1=A4=F1=B9=
=EF=A6r=A6=EA=A4=A4p-n+1=A6=DCp=AA=BA=AD=C8=ACO=A7_=BBP=C3=F6=C1=E4=A6r=AC=
=DB=A6P=A1C=20
<BR>
<DIV style=3D"TEXT-ALIGN: center"><IMG title=3D=A6r=A6=EA=AE=D6=B9=EF=20
style=3D"WIDTH: 271px; HEIGHT: 87px" alt=3D=A6r=A6=EA=AE=D6=B9=EF=20
src=3D"http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip/=
images/matchString-1.jpg"><BR><BR>
<DIV=20
style=3D"TEXT-ALIGN: =
left">=A8=BA=BB=F2=ABe=B6i=AA=ED=B8=D3=A6p=A6=F3=ABe=B6i=A1A=C1|=AD=D3=B9=
=EA=BB=DA=AA=BA=A8=D2=A4l=A1A=A6p=AAG=ADn=A6b=A6r=A6=EA=A4=A4=B7j=B4MJUST=
=B3o=AD=D3=A6r=A6=EA=A1A=ABh=A5i=AF=E0=B9J=A8=EC=AA=BA=B4X=AD=D3=B1=A1=AA=
p=A6p=A4U=A9=D2=A5=DC=A1G<BR>
<DIV style=3D"TEXT-ALIGN: center"><IMG title=3D=A6r=A6=EA=AE=D6=B9=EF=20
style=3D"WIDTH: 364px; HEIGHT: 367px" alt=3D=A6r=A6=EA=AE=D6=B9=EF=20
src=3D"http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip/=
images/matchString-2.jpg"><BR><BR><BR></DIV>=A8=CC=B7=D3=B3o=AD=D3=A8=D2=A4=
l=A1A=A5i=A5H=A8M=A9w=A5X=A7=DA=AD=CC=AA=BA=ABe=B6i=AD=C8=AA=ED=A6p=A4U=A1=
G=20
<BR>
<TABLE style=3D"WIDTH: 313px; HEIGHT: 102px; TEXT-ALIGN: left" =
cellSpacing=3D2=20
cellPadding=3D2 border=3D1>
<TBODY>
<TR>
<TD>=A8=E4=A5=A6</TD>
<TD>J</TD>
<TD>U</TD>
<TD>S</TD>
<TD>T</TD></TR>
<TR>
<TD>4</TD>
<TD>3</TD>
<TD>2</TD>
<TD>1</TD>
=
<TD>4=A1]match?=A1^</TD></TR></TBODY></TABLE><BR>=A6p=AAG=C3=F6=C1=E4=A6r=
=A4=A4=A6=B3=AD=AB=BD=C6=A5X=B2{=AA=BA=A6r=A4=B8=A1A=ABh=ABe=B6i=AD=C8=B4=
N=B7|=A6=B3=A8=E2=AD=D3=A5H=A4W=AA=BA=AD=C8=A1A=A6=B9=AE=C9=ABh=A8=FA=ABe=
=B6i=AD=C8=B8=FB=A4p=AA=BA=AD=C8=A1A=A6p=A6=B9=B4N=A4=A3=B7|=B8=F5=B9L=A5=
i=AF=E0=AA=BA=A6=EC=B8m=A1A=A8=D2=A6ptexture=B3o=AD=D3=C3=F6=C1=E4=A6r=A1=
At=AA=BA=ABe=B6i=AD=C8=C0=B3=B8=D3=A8=FA=AB=E1=AD=B1=AA=BA3=A6=D3=A4=A3=AC=
O=A8=FA=ABe=AD=B1=AA=BA7=A1C<BR>
<H2>=B9=EA=A7@</H2>
<UL>
<LI>C </LI></UL><PRE>#include <stdio.h> <BR>#include =
<stdlib.h> <BR>#include <string.h> <BR><BR>void =
table(char*); // =AB=D8=A5=DF=ABe=B6i=AA=ED <BR>int search(int, char*, =
char*); // =B7j=B4M=C3=F6=C1=E4=A6r <BR>void substring(char*, char*, =
int, int); // =A8=FA=A5X=A4l=A6r=A6=EA <BR><BR>int skip[256]; =
<BR><BR>int main(void) { <BR> char str_input[80]; <BR> char =
str_key[80]; <BR> char tmp[80] =3D {'\0'}; <BR> int m, n, p; =
<BR><BR> printf("=BD=D0=BF=E9=A4J=A6r=A6=EA=A1G"); <BR> =
gets(str_input); <BR> =
printf("=BD=D0=BF=E9=A4J=B7j=B4M=C3=F6=C1=E4=A6r=A1G"); <BR> =
gets(str_key); <BR><BR> m =3D strlen(str_input); // =
=ADp=BA=E2=A6r=A6=EA=AA=F8=AB=D7 <BR> n =3D strlen(str_key); <BR> =
table(str_key); <BR> p =3D search(n-1, str_input, str_key); <BR><BR> =
while(p !=3D -1) { <BR> substring(str_input, tmp, p, m); <BR> =
printf("%s\n", tmp); <BR> p =3D search(p+n+1, str_input, =
str_key); <BR> } <BR><BR> printf("\n"); <BR><BR> return 0; =
<BR>} <BR><BR>void table(char *key) { <BR> int k, n; <BR><BR> n =
=3D strlen(key); <BR><BR> for(k =3D 0; k <=3D 255; k++) <BR> =
skip[k] =3D n; <BR> for(k =3D 0; k < n - 1; k++) <BR> =
skip[key[k]] =3D n - k - 1; <BR>} <BR><BR>int search(int p, char* input, =
char* key) { <BR> int i, m, n; <BR> char tmp[80] =3D {'\0'}; =
<BR><BR> m =3D strlen(input); <BR> n =3D strlen(key); <BR><BR> =
while(p < m) { <BR> substring(input, tmp, p-n+1, p); <BR> =
<BR> if(!strcmp(tmp, key)) // =
=A4=F1=B8=FB=A8=E2=A6r=A6=EA=ACO=A7_=AC=DB=A6P <BR> return =
p-n+1; <BR> p +=3D skip[input[p]]; <BR> } <BR><BR> return =
-1; <BR>} <BR><BR>void substring(char *text, char* tmp, int s, int e) { =
<BR> int i, j; <BR><BR> for(i =3D s, j =3D 0; i <=3D e; i++, =
j++) <BR> tmp[j] =3D text[i]; <BR><BR> tmp[j] =3D '\0'; <BR>} =
<BR></PRE><BR>
<UL>
<LI>Java </LI></UL><PRE>import java.io.BufferedReader;<BR>import =
java.io.IOException;<BR>import java.io.InputStreamReader;<BR><BR>public =
class StringMatch {<BR> private int[] skip;<BR> private int p;<BR> =
private String str;<BR> private String key;<BR> <BR> public =
StringMatch(String key) {<BR> skip =3D new int[256];<BR> =
this.key =3D key;<BR> <BR> for(int k =3D 0; k <=3D 255; =
k++) <BR> skip[k] =3D key.length(); <BR> for(int k =3D =
0; k < key.length() - 1; k++) <BR> skip[key.charAt(k)] =3D =
key.length() - k - 1; <BR> }<BR> <BR> public void search(String =
str) {<BR> this.str =3D str;<BR> p =3D =
search(key.length()-1, str, key);<BR> }<BR> <BR> private int =
search(int p, String input, String key) { <BR> while(p < =
input.length()) { <BR> String tmp =3D input.substring(<BR> =
p-key.length()+1, p+1); <BR><BR> =
if(tmp.equals(key)) // =A4=F1=B8=FB=A8=E2=A6r=A6=EA=ACO=A7_=AC=DB=A6P =
<BR> return p-key.length()+1; <BR> p +=3D =
skip[input.charAt(p)]; <BR> } <BR><BR> return -1; <BR> =
}<BR> <BR> public boolean hasNext() {<BR> return (p !=3D =
-1);<BR> }<BR> <BR> public String next() {<BR> String =
tmp =3D str.substring(p);<BR> p =3D search(p+key.length()+1, str, =
key);<BR> return tmp;<BR> }<BR> <BR> public static void =
main(String[] args) <BR> throws =
IOException {<BR> BufferedReader bufReader =3D <BR> =
new BufferedReader(<BR> new =
InputStreamReader(System.in));<BR> <BR> =
System.out.print("=BD=D0=BF=E9=A4J=A6r=A6=EA=A1G");<BR> String =
str =3D bufReader.readLine();<BR> =
System.out.print("=BD=D0=BF=E9=A4J=B7j=B4M=C3=F6=C1=E4=A6r=A1G"); <BR> =
String key =3D bufReader.readLine();<BR> <BR> =
StringMatch strMatch =3D new StringMatch(key);<BR> =
strMatch.search(str);<BR><BR> while(strMatch.hasNext()) { <BR> =
System.out.println(strMatch.next()); <BR> } <BR> =
}<BR>} </PRE><BR><BR></DIV></DIV></BODY></HTML>
------=_NextPart_000_0056_01C6D6D1.8DC3B4C0
Content-Type: image/jpeg
Content-Transfer-Encoding: base64
Content-Location: http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip/images/matchString-1.jpg
/9j/4AAQSkZJRgABAgAAAQABAAD/2wBDAAgGBgcGBQgHBwcJCQgKDBQNDAsLDBkSEw8UHRofHh0a
HBwgJC4nICIsIxwcKDcpLDAxNDQ0Hyc5PTgyPC4zNDL/2wBDAQkJCQwLDBgNDRgyIRwhMjIyMjIy
MjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjL/wAARCABXAQ8DASIA
AhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQA
AAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3
ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWm
p6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEA
AwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSEx
BhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElK
U1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3
uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwD3+iii
gAooooAKKKKACgjIIooPQ0AcT4n1/XdP8beG9D0ubTYoNYW5DSXNo8rRNCm8n5ZUBByBjjGM5OcC
/wCD/Ec3iO31VbiCOKbStSl02Ro2O2VoguZAp+4CWOFy2P7xrI8WeGrjxD8QvCks2jJe6NYJdm8k
uPLaLMkeEXYx3EhlH8JA3DB646i70WWS3trfTtUutIgt02LHYxQbSuAFGJI3AAAwAuOvfjABy+se
NNR8P/EFLG/htf8AhGTBC09+EZGspJWkWPzW3EFGeEjdtVRvGTxluistQu38W6ppsxga1gtbW5t9
kZV18wzIysdxDcw5BAH3sc4zUEGnS3Xi3XZLzT86dcafa2amYIyXG1rhpBtyTtxKoO4DJzwRyec8
H+BdR0O+1zTdS1G6vdIe3tYNMuFuWinjhjeZ/KZ4yrgoXAyDgqQBgfKoB3NnqcF/dajbRpIHsbgW
8pYDDMYkk+XB6YkUc45B+tUrPUbyXxdqulzRQLbW1ra3EDoxLv5rTK27IAGDFgAZ9c84XH0PwdBZ
a1q11K+qqrahHPa51e5YSIsEI3OvmHf86OvzgkgAfdxWrZW91/wm2sXslpJFaPZWdvDM7LiZkad3
KgEkAeao+YDnOMjmgDdooooAKKKKACiiigAooooAy9R8S6Fo9wtvqetadYzsnmCO5ukjYrkjOGI4
yCM+xq/b3MN3bxXFvKksMqB45I2DK6kZBBHBBHINed+OXvE+J/w+bT4IJ7n/AImOxJ5jEjfuUzlg
jEcZ6Kea6Twf4Zm8OW+qNcXEcs+p6lLqUiRg7YWlC5jDHlwCp+Yhc9dooA6WiiigAooooAKKKKAC
iiigAooooAztS1/R9GMX9qarZWPmgmP7VcJFvAxnG4jOMj8xVD/hO/B//Q16H/4MIv8A4qkvB/xc
LRv+wVfn/wAi2ldD+FAHP/8ACd+D/wDoa9D/APBhF/8AFUf8J34P/wChr0P/AMGEX/xVdB+FH4UA
c/8A8J34P/6GvQ//AAYRf/FUf8J34P8A+hr0P/wYRf8AxVdB+FH4UAc//wAJ34P/AOhr0P8A8GEX
/wAVR/wnfg//AKGvQ/8AwYxf/FV0H4UfhQBzg8c+Dwf+Rr0L/wAGEX/xVP8A+E78H4/5GvQ//BhF
/wDFV0H4Vz/jrj4e+JT/ANQq6/8ARTUAM/4TnwiCQfFWhj2OoQ//ABVH/Cc+ECcnxVof/gwh/wDi
q6ELgADgDoBxXP6+uNb8KDrnVX6/9eVzQMB458IDP/FV6F/4MIf/AIqgeOvCAP8AyNmh/wDgwi/+
Krovwo/CgDn/APhO/B//AENeh/8Agwi/+Ko/4Tvwf/0Neh/+DCL/AOKroPwo/CgRz/8Awnfg/wD6
GvQ//BhF/wDFUf8ACd+D/wDoa9D/APBhF/8AFV0H4UfhQBz/APwnfg//AKGvQ/8AwYRf/FUf8J34
P/6GvQ//AAYRf/FV0H4UfhQBz/8Awnfg/wD6GvQ//BhF/wDFUHx34PIx/wAJXof/AIMIv/iq6D8K
SgDirjWPh9eeILHXLjxHo8moWKuttJ/a67YwwIbCb9uSDycZwBzwK1v+E88H/wDQ16H/AODCL/4q
m+Dlzolzn/oK6j/6Wzf1p3jrj4e+JT/1Crr/ANFNQAf8J34QBwfFOiD66hD/APFUf8J34P8A+hr0
P/wYRf8AxVbwXAA6AdAOKd+FAHP/APCd+D/+hr0P/wAGEX/xVH/Cd+D/APoa9D/8GEX/AMVXQfhR
+FAHP/8ACd+D/wDoa9D/APBhF/8AFUf8J34P/wChr0P/AMGEX/xVdB+FH4UAc/8A8J34P/6GvQ//
AAYRf/FUf8J34P8A+hr0P/wYRf8AxVdB+FH4UAc//wAJ34P/AOhr0P8A8GMX/wAVWlp+s6Zq9s1z
pmoWt9ArlGltplkUMADglSQDgjj3q7XP+HhnXPFftqqf+kdrQAXZ/wCLhaN/2Cr8f+RbOuhrK1Tw
9Yaxc29xdC6We3R44pLa9mt2VXKlhmNlyCUXr6VU/wCEN0z/AJ+tc/8AB7e//HqAOgorn/8AhDdM
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -