KMP算法

• 第三次更新

#include<iostream>
#include<cstring>
#include<stdlib.h>
using namespace std;
int next[15]={-1};
void getnext(char t[])
{
	int j,i,k,n,m;
	m=strlen(t);
	j=0;k=-1;
	while(j<m-1)
	{
		if(k==-1||t[j]==t[k])
		{
			j++;
			k++;
			next[j]=k;
		}
		else k=next[k];
	}
	for(i=0;i<m;i++)
	cout<<next[i]<<' ';
	cout<<endl;
}
int KMPmatching(char *s,char *t)
{
	int i,j;
	i=0;
	j=0;
	int m,n;
	m=strlen(s);
	n=strlen(t);
	while(i<m&&j<n)
	{
		if(j==-1||s[i]==t[j])
		{
			i++;
			j++;
		}
		else j=next[j];
	}
	if(j>=n) return i-n;
	else return -1;
}


int main()
{
	char a[20]="abcaababc";
	char b[20]="aba";
	getnext(b);
	cout<<KMPmatching(a,b);
}