📄 csdn_文档中心_我写的kmp 算法.htm
字号:
<TR bgColor=#999999>
<TD colSpan=3 height=1></TD></TR></TBODY></TABLE>
<TABLE border=0 width=770>
<TBODY>
<TR>
<TD align=middle bgColor=#fafafa class=td1 vAlign=top width=150><BR>
<SCRIPT src="CSDN_文档中心_我写的KMP 算法.files/microsoft.js"></SCRIPT>
</TD>
<TD align=middle width=620>
<TABLE bgColor=#eeeeee border=0 cellPadding=0 cellSpacing=0 width=600>
<TBODY>
<TR bgColor=#ffffff>
<TD align=middle height=10 width=50></TD>
<TD align=right><A href="http://www.csdn.net/">CSDN</A> - <A
href="http://www.csdn.net/develop/">文档中心</A> - <FONT
color=#003399>Visual C++</FONT> </TD></TR>
<TR>
<TD align=middle height=5></TD>
<TD align=middle width=500></TD></TR>
<TR>
<TD align=middle bgColor=#003399 height=10><FONT
color=#ffffff>标题</FONT></TD>
<TD><B> 我写的KMP
算法</B> jjduan185（原作） </TD></TR>
<TR>
<TD align=middle height=5></TD>
<TD align=middle width=500></TD></TR>
<TR>
<TD align=middle bgColor=#003399><FONT color=#ffffff>关键字</FONT></TD>
<TD width=500> KMP</TD></TR>
<TR>
<TD align=middle height=5></TD>
<TD align=middle width=500></TD></TR></TBODY></TABLE><!--文章说明信息结束//-->
<TABLE border=0 width=600>
<TBODY>
<TR>
<TD align=left><BR>
<P>#include<iostream><BR>#include<time.h><BR>#include<string><BR>using
namespace std;<BR>void init(string ,string);<BR>void show(char
[],int);<BR>int kmp(string ,string,int pos);<BR>void
get_next(char*,int *);<BR>string s1,t1;<BR>int m,n;<BR>char
*s;<BR>char *t;<BR>int
*next;<BR>/*************************MAIN**************************************/<BR>int
main(int argc[],char*args[])<BR>{<BR>
<BR> double
t=clock();<BR> cout<<"找到位置为："<<kmp("acbsabcaacabaabaabcacaabc","abaabca",1)<<endl;<BR>
delete[] s;<BR> delete[]
next;<BR> cout<<"耗时："<<(clock()-t)/1000<<"毫秒！"<<endl;<BR> return
0;<BR>}
<BR>/**********************++++NEXT++++********************************/<BR>void
get_next(char s[],int ne[])<BR>{<BR> ne =new
int[n+1];<BR> next=new
int[n+1];<BR> ne[0]=9999;<BR>
int i(1),j(0);<BR> ne[1]=0;<BR>
while(i<=(int)(t[0]))//数组是字符型的，要转化为整数<BR> {<BR>
if(j==0||t[i]==t[j]){++i;++j;ne[i]=j;}<BR>
else j=ne[j];<BR> }<BR> for(
i=1;i<=n;i++)<BR> {<BR>
cout<<"next["<<i<<"]="<<ne[i]<<endl;<BR>
next[i]=ne[i];<BR>
}<BR>}<BR>/********************++++KMP+++**********************************/<BR>
int kmp(string s0,string t0,int pos)<BR>
{<BR>
init(s0,t0);<BR> int
i=pos,j=1;<BR>
while(i<=((int)(s[0]))&&(j<=((int)(t[0]))))<BR> {<BR>
if((j==0)||(s[i]==t[j])){++i;++j;}<BR>
else j=next[j];<BR>
<BR> }<BR>
if(j>(int)(t[0])) return
i-((int)(t[0]));<BR> else
return 0;</P>
<P>
}<BR>/***************++++INIT+++*****************************************/<BR>
void init(string ss,string
tt)<BR> {<BR>
//cout<<"请输入原串S=：
"<<endl;<BR>
//cin>>s1;<BR>
//cout<<"请输入模式串T=："<<endl;<BR>
//cin>>t1;<BR>
s1=ss;<BR>
t1=tt;<BR> m=s1.length();
<BR>
n=t1.length();<BR>
//if((s=(char*)malloc((m+1)*sizeof(char)))<0){cout<<"failed\n";return;}<BR>
s=new char[m+1];<BR>
s[0]=m;<BR> //if((t=(char*)
malloc((n+1)*sizeof(char)))<0)
{cout<<"failed\n";return;}<BR>
t=new char[n+1];<BR>
t[0]=n;<BR> for(int
i=1;i<=m;i++)<BR>
s[i]=s1.at(i-1);<BR> for(
i=1;i<=n;i++)<BR>
t[i]=t1.at(i-1);<BR>
cout<<"原串为： ";
show(s,m);<BR> cout<<"模式串为： ";
show(t,n);<BR>
get_next(t,next);
<BR> }<BR>/*******************++++SHOW+++**************************************/<BR>
void show(char s[],int n )<BR>
{<BR> for(int
i=1;i<=n;i++)<BR>
cout<<s[i]<<"
";<BR>
cout<<endl;<BR>
cout<<"长度为：
"<<int(s[0])<<"\n";<BR>
}<BR></P><BR></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><BR>
<TABLE align=center bgColor=#006699 border=0 cellPadding=0 cellSpacing=0
width=770>
<TBODY>
<TR bgColor=#006699>
<TD align=middle bgColor=#006699 id=white><FONT
color=#ffffff>对该文的评论</FONT></TD>
<TD align=middle>
<SCRIPT src="CSDN_文档中心_我写的KMP 算法.files/readnum.htm"></SCRIPT>
</TD></TR></TBODY></TABLE><BR>
<DIV align=center>
<TABLE align=center bgColor=#cccccc border=0 cellPadding=2 cellSpacing=1
width=770>
<TBODY>
<TR>
<TH bgColor=#006699 id=white><FONT
color=#ffffff>我要评论</FONT></TH></TR></TBODY></TABLE></DIV>
<DIV align=center>
<TABLE border=0 width=770>
<TBODY>
<TR>
<TD>你没有登陆，无法发表评论。 请先<A
href="http://www.csdn.net/member/login.asp?from=/Develop/read_article.asp?id=27392">登陆</A>
<A
href="http://www.csdn.net/expert/zc.asp">我要注册</A><BR></TD></TR></TBODY></TABLE></DIV><BR>
<HR noShade SIZE=1 width=770>
<TABLE border=0 cellPadding=0 cellSpacing=0 width=500>
<TBODY>
<TR align=middle>
<TD height=10 vAlign=bottom><A
href="http://www.csdn.net/intro/intro.asp?id=2">网站简介</A> - <A
href="http://www.csdn.net/intro/intro.asp?id=5">广告服务</A> - <A
href="http://www.csdn.net/map/map.shtm">网站地图</A> - <A
href="http://www.csdn.net/help/help.asp">帮助信息</A> - <A
href="http://www.csdn.net/intro/intro.asp?id=2">联系方式</A> - <A
href="http://www.csdn.net/english">English</A> </TD>
<TD align=middle rowSpan=3><A
href="http://www.hd315.gov.cn/beian/view.asp?bianhao=010202001032100010"><IMG
border=0 height=48 src="CSDN_文档中心_我写的KMP 算法.files/biaoshi.gif"
width=40></A></TD></TR>
<TR align=middle>
<TD vAlign=top>百联美达美公司 版权所有 京ICP证020026号</TD></TR>
<TR align=middle>
<TD vAlign=top><FONT face=Verdana>Copyright © CSDN.net, Inc. All rights
reserved</FONT></TD></TR>
<TR>
<TD height=15></TD>
<TD></TD></TR></TBODY></TABLE></DIV>
<DIV></DIV><!--内容结束//--><!--结束//--></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -