## KMP算法

2017年11月15日 ⁄ 综合 ⁄ 共 1273字 ⁄ 字号 评论关闭
```#include <iostream>
using namespace std;

void originalMatch(char* o,char* m)
{
int original = strlen(o);
int match = strlen(m);
if (match > original||match ==0||original == 0)
{
cout<<"length is incorrect!"<<endl;
return;
}
bool haveornot = true;
for (auto i =0;i<original-match+1;i++)
{
bool flag = true;
for (auto j =0;j < match;j++)
{
if(o[i+j]!=m[j])
{
flag =false;
break;
}
}
if (flag)
{
haveornot =false;
cout<<"find the match string,the place is "<<i+1<<endl;
}
}
if (haveornot)
{
cout<<"there is no string \""<<m<<"\" in the string \""<<o<<"\"!"<<endl;
}
}

void Kmp(char* o,char* m)
{
int original = strlen(o);
int match = strlen(m);
if (match > original||match ==0||original == 0)
{
cout<<"length is incorrect!"<<endl;
return;
}
int* a =new int[match];
int q = 0;
a[0] = 0;
bool haveornot = true;
for (auto i =1;i<match;i++)
{
while(q>0&&m[q]!=m[i])
q =  a[q];
if (m[q] == m[i])
q++;
a[i] = q;
}
q=0;
for (auto i =0;i<original;i++)
{
while(q>0&&m[q]!=o[i])
q =  a[q-1];//减一是为了保证前面已匹配的  向右移动的位数，q加1表示匹配位置，运行到这时q表示匹配不成功所以移动前面的
if (m[q] == o[i])
q++;
if (q == match)
{
haveornot =false;
cout<<"find the match string,the place is "<<(i-q+1)+1<<endl;
q=a[q-1];//保证匹配成功后面所要移动的位置
//此处不需要保证i的后移，因为i后移了就会使成立m[q]!=o[i]
}
}
if (haveornot)
{
cout<<"there is no string \""<<m<<"\" in the string \""<<o<<"\"!"<<endl;
}
delete []a;
}
void main()
{