// exam1.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

void get_next(int* &next,char* s)
{
	int j=0;
	int i=1;

	int len=strlen(s);
	next=(int*)malloc(len*sizeof(int));
	memset(next,0,len*sizeof(int));

	while(s[i]!='\0')
	{
		if(s[j]==s[i])
		{
			i++;
			j++;
			if(s[i]!=s[j])
			{
				next[i]=j;
			}
			else
			{
				next[i]=next[j];
			}
		}
		else
		{
			if(j==0)
			{
				i++;
			}
			j=next[j];
		}
	}
}

int kmp(int* next,char* s,char* m)
{
	int i=0,j=0;

	while(s[i]!='\0')
	{
		if(m[j]=='\0')
		{
			break;
		}
		if(s[i]==m[j])
		{
			i++;
			j++;
		}
		else
		{
			if(j==0)
			{
				i++;
			}
			j=next[j];
		}
	}

	return i-strlen(m);
}

int main(void)
{
	int len,*next;
	char *s="acabaabaabcacaabc";
	char *m="abaabcac";
	len=strlen(m);

	get_next(next,m);
	int loc=kmp(next,s,m);

	/*for(int i=0;i<len;i++)
	{
		cout<<next[i]<<endl;
	}*/
	cout<<loc<<endl;

	system("pause");
	return 0;
}