改进的KMP算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了改进的KMP算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2956字，纯文字阅读大概需要5分钟。

内容图文

原文链接：http://www.cnblogs.com/zhuy/archive/2012/04/09/2439652.html

 

//C.h 几乎各程序都需要用到的文件包含宏命令和使用名空间
#ifndef _C_H_
#define _C_H_
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <cstdarg>
#include <assert.h>
using namespace std;
#endif

#include "C.h"
class HString
{
private:
char *ch;
int length;

public:
HString()
{
ch=NULL;
length=0;
}

HString(const char *str)
{
length=strlen(str);

ch=new char[length];

assert(ch!=NULL);

for (int i=0;i<length;i++)
{
ch[i]=str[i];
}

}

HString(const HString &S)
{
length=S.length;
ch=new char[length];
for (int i=0;i<length;i++)
{
ch[i]=S.ch[i];
}
}

~HString()
{//析构函数;
ClearString();
}

void ClearString()
{//清空字符串;
if (ch!=NULL)
{
delete [] ch;
ch=NULL;
}

length=0;
}

void StrAssign(const char *str)
{//产生与源字符串相同的串;
ClearString();//释放原有空间;

length=strlen(str);

if (length)
{
ch=new char [length];

assert(ch!=NULL);

for (int i=0;i<length;i++)
{
ch[i]=str[i];
}
}
}

// bool StrEmpty() const//判断字符串是否为空;
// {//如果为空则返回True,否则返回False;
// return length==0;
// }
int compare(const HString &S) const
{
for (int i=0;i<length&&i<S.length;++i)
if (ch[i]!=S.ch[i])
return ch[i]-S.ch[i];

return length-S.length;
}

int StrLength() const
{//返回串长;
return length;
}

bool substring(HString &sub,int pos,int len) const
{
if (pos<1||pos>length||len<0||len>length-pos+1)
{
return false; 
sub.ClearString();
}

 

if (len)//字串非空;
{
sub.ch=new char[len];

assert(sub.ch!=NULL);

for (int i=0;i<len;i++)
{
sub.ch[i]=ch[pos-1+i];
}
sub.length=len;
}
return true;
}

 


};

void getnext (HString S,int next[])
{//求next数组的值

int i=1,j=0;
HString sub1,sub2;
next[1]=0;//s的第一个字符与主模式串失配时，主串的下一个字符与s的第一个字符比较;
while (i<S.StrLength())
{
S.substring(sub1,i,1);//s的第i个字符在sub1中;
S.substring(sub2,j,1);//s的第j个字符在sub2中;
if (j==0||sub1.compare(sub2)==0)
{
++i;
++j;
S.substring(sub1,i,1);
S.substring(sub2,j,1);
if (sub1.compare(sub2)!=0)
next[i]=j;
else
next[i]=next[j];
}
else
j=next[j];
}
}

int Index_KMP(HString T,HString S,int pos,int next[])//匹配过程;
{
int i=pos,j=1;

HString sub1,sub2;

while (i<=T.StrLength()&&j<=S.StrLength())
{
T.substring(sub1,i,1);
S.substring(sub2,j,1);

if (j==0||sub1.compare(sub2)==0)
{
++i;
++j;
}
else
j=next[j];
}
if (j>S.StrLength())
{
return i-S.StrLength();
}

else
return 0;

}

void main()
{
int i,*p;
HString s1("abcdabcdefg"),s2("abcde");

p=new int[s2.StrLength()+1];

getnext(s2,p); //求得s2的next数组，存在p数组中;

for ( i=1;i<=s2.StrLength();i++)
{
cout<<*(p+i);
}
cout<<endl;

i=Index_KMP(s1,s2,1,p);

if (i)
{
cout<<"子串与主串在"<<i<<"处配对"<<endl;
}
else
cout<<"子串与主串匹配不成功!"<<endl;
}

个人觉得改进的KMP算法中最重要的就是求next数组，只要掌握了next数组的求法，该算法的精髓就被掌握了

转载于:https://www.cnblogs.com/zhuy/archive/2012/04/09/2439652.html

内容总结

以上是互联网集市为您收集整理的改进的KMP算法全部内容，希望文章能够帮你解决改进的KMP算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---