学步园

#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()
{
	char o[100] = "anwsanwwqeasdfaanwsanwadadwanwsanwsanw";
	char m[100] ="anwsanw";
	originalMatch(o,m);
	cout<<"kmp\n";
	Kmp(o,m);
	system("pause");
}