字符串模式匹配（所谓的kmp)算法

#include<assert.h>

#include<iostream>

#include<fstream>

#include<time.h>

#include<stack>

#include<string>

using namespace std;



inline  unsigned __int64 getclock()

{

	__asm

	{

		rdtsc;

	}

}



const char Min='a';

const int characters=26;

int *shiftTable=new int[characters];

//žùŸÝģʜarrŽŽœšÒÆλ±í

//@param  arr,³€¶ÈΪmµÄģʜ×ÖŽ® 



void shiftTalble(char *& const arr,int m)

{

	for(int i=0;i<characters;i++)

	{

		shiftTable[i]=m;

	}

	for(int i=0;i<m-1;i++)

	{

		shiftTable[arr[i]-Min]=m-1-i;

	}

}

//ÔÚtext×Ö·ûŽ®ÖвéÕÒarr

//@param  text£¬³€¶ÈΪnµÄÎıŸ   arr,³€¶ÈΪmµÄģʜ

//Èç¹û³É¹Š£¬·µ»ØÆ¥ÅäµÄÊ××ÖĞλÖ㬠Èç¹û²»³É¹Š£¬·µ»Ø-1

int find( char *& const text,int n,char *& const arr,int m)

{

	assert(text!=NULL&&arr!=NULL);

	shiftTalble(arr,m);

	int i=m-1;

	int j;

	int k;

	while(i<n)

	{

		j=m-1;

		k=i;

		while(j>=0&&text[k]==arr[j])

		{

			j--;

			k--;

		}

		if(j<0)  //find 

		{

			return k+1;

		}

		else

		{

			i+=shiftTable[text[i]-Min];

		}

	}

	return -1; //fail

}

int main()

{

	



	srand((unsigned int) time(0));

	int n=rand()%250+250;

	int m=8;

	char *text=new char [n];

	int i;

	for( i=0;i<n/2;i++)

	{

		text[i]=Min+rand()%characters;

	}

	text[i++]='m';

	text[i++]='a';

	text[i++]='z';

	text[i++]='h';

	text[i++]='e';

	text[i++]='n';

	text[i++]='g';

	for(;i<n-1;i++)

	{

		text[i]=Min+rand()%characters;

	}

	text[n-1]='\0';

	

	char *arr=new char[m];

	/*for(int i=0;i<m-1;i++)

	{

		arr[i]=Min+rand()%characters;

	}

	arr[m-1]='\0';*/

	arr="mazheng";

	cout<<text<<endl;

	cout<<arr<<endl;

	int start=getclock();

	int f1=find(text,n-1,arr,m-1);

	int final=getclock();

	cout<<f1<<"   "<<final-start<<endl;

	string s=text;

	string p=arr;

	start=getclock();

	int f2=s.find(arr);

	final=getclock();

	cout<<f2<<"  "<<final-start<<endl;

	

	

	return 0;

}